题目：
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 by :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.
链接：
题解：
其实我还加这哥们LinkedIn了...后来他被Apple录取了，挺好的。 使用Recursive比较快就能写出来。
Time Complexity - O(n)， Space Complexity - O(n)。
/** * 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 root; TreeNode left = root.left; root.left = invertTree(root.right); root.right = invertTree(left); return root; }}
二刷：
使用递归求解比较方便。先保存左子树，，再更新左子树和右子树，最后返回root。
Java:
Time Complexity - O(n)， Space Complexity - O(n)。
/** * 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 root; } TreeNode tmpLeft = root.left; root.left = invertTree(root.right); root.right = invertTree(tmpLeft); return root; }}
使用一个stack来迭代
/** * 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 root; } LinkedList stack = new LinkedList<>(); stack.addLast(root); while (stack.size() > 0) { TreeNode node = stack.pollLast(); if (node != null) { TreeNode tmp = node.left; node.left = node.right; node.right = tmp; stack.addLast(node.left); stack.addLast(node.right); } } return root; }}
三刷：
Java:
/** * 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 root; } TreeNode tmpLeft = root.left; root.left = invertTree(root.right); root.right = invertTree(tmpLeft); return root; }}
使用一个stack来模拟系统栈， 用Queue也可以。 以后我决定在面试里就写stack，不用Doubly LinkedList了。这样表达更清晰。自己清楚Stack是继承自vector，并且是depricated就可以了，在production上不用, 面试时提一下。
/** * 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 root; } Stack stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node != null) { TreeNode tmpLeft = node.left; node.left = node.right; node.right = tmpLeft; stack.push(node.left); stack.push(node.right); } } return root; }}
用Queue的
/** * 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 root; Queue q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { TreeNode node = q.poll(); if (node != null) { q.offer(node.left); q.offer(node.right); TreeNode tmp = node.left; node.left = node.right; node.right = tmp; } } return root; }}
Reference:
https://leetcode.com/discuss/40001/straightforward-dfs-recursive-iterative-bfs-solutions
https://leetcode.com/discuss/40051/3-4-lines-python