Question
Invert a binary tree. 翻转二叉树
4 4
/ \ / \
2 7 to 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1
这题的槽点是
This problem was inspired by [this original tweet](https://twitter.com/mxcl/status/608682016205344768) by [Max Howell](https://twitter.com/mxcl)
Solution
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root != null) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
}
return root;
}
}
Point
- 递归的四条基本法则
- 基准情形（base case）
必须总要有某些基准的情形，它们不用递归就能求解 - 不断推进（making progress）
对于那些要递归求解的情形，递归调用必须总能朝着一个基准情形推进。 - 设计法则 （design rule）
假设所有的递归调用都能运行 - 和成效益法则（compound interest rule）
求解一个问题的同意实例时，切勿在不同的递归中做重复性工作。
- 基准情形（base case）
