翻转二叉树。Google的热身题。会写翻转二叉树你就比Max Howell强了。。
我的递归DFS代码:
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
另一种递归DFS代码:
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
final TreeNode left = root.left,
right = root.right;
root.left = invertTree(right);
root.right = invertTree(left);
return root;
}
}
另外这题用Stack和Queue都能解。
用Queue就是BFS。
Stack就是DFS! Stack执行过程跟递归DFS一样(DFS本身就是一层层的,神奇)。
详见:
https://leetcode.com/problems/invert-binary-tree/#/solutions
网友评论