Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:
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.
题目标签:Tree
这道题目给了我们一个二叉树,让我们把它反转一下。对于每一个点,它的左边和右边子树需要对调一下。利用postOrder 来遍历树,当走到最低端的时候,点 == null, 返回null, 对于每一个点,把它的left 和right 互换一下。return 这个点。
Java Solution:
Runtime beats 27.97%
完成日期:07/04/2017
关键词:Tree
关键点:把left 和right 互换
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution
{
public TreeNode invertTree(TreeNode root)
{
if(root == null)
return null; // continue children
invertTree(root.left);
invertTree(root.right); // swap left and right
TreeNode temp;
temp = root.left;
root.left = root.right;
root.right = temp; return root;
}
}
参考资料:N/A
LeetCode 算法题目列表 - LeetCode Algorithms Questions List