Invert a binary tree.
4 / 2 7 / / 1 3 6 9to
4 / 7 2 / / 9 6 3 1Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
翻转二叉树
/**
* 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;
var tem = root.left;
root.left = root.right;
root.right = tem;
if(root.right!=null){
InvertTree(root.right);
}
if(root.left!=null){
InvertTree(root.left);
}
return root;
}
}
payhon BFS版
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if (not root):
return
queue = [root]
while (queue):
node = queue.pop(0)
node.left,node.right = node.right,node.left
if(node.left):
queue.append(node.left)
if(node.right):
queue.append(node.right)
return root