/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode InvertTree(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) return root; TreeNode left = root.left;
root.left = InvertTree(root.right);
root.right = InvertTree(left);
return root;
}
}
https://leetcode.com/problems/invert-binary-tree/#/description
补充一个使用层次遍历处理的方案，java实现
class Solution {
public TreeNode invertTree(TreeNode root) {
List<TreeNode> nodes = new LinkedList<>();
if (root != null) {
nodes.add(root);
}
while (!nodes.isEmpty()) {
int numNodes = nodes.size();
while (numNodes > 0) {
TreeNode node = nodes.remove(0);
// push children to the next layer by appending to the end of the list
if (node.left != null) {
nodes.add(node.left);
}
if (node.right != null) {
nodes.add(node.right);
}
// flip
TreeNode left = node.left;
node.left = node.right;
node.right = left;
numNodes--;
}
}
return root;
}
}补充一个python的实现：
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root == None:
return None
left = root.left
root.left = self.invertTree(root.right)
root.right = self.invertTree(left)
return root