今天是二叉树的第二天！
题目链接：226. 翻转二叉树
状态：第一次没写出来，看解析后做到AC。
看到题目时第一想法：没有什么思路，甚至都不知道翻转二叉树实际上就是交换每个节点的左右子节点。于是就直接看了解析，然后发现交换左右子节点就是交换TreeNode的连接，于是就恍然大悟。
至于使用递归法嘛，关键还是递归三部曲：确定递归函数的参数和返回值、确定终止条件、确定单层递归的逻辑。在本题中，1. 题目要求返回根节点root，那就正好把TreeNode作为方法的返回值。至于参数的话，就传入节点的指针就好。2. 终止条件就是在往深层次遍历的过程中，遍历到空节点就返回。3. 单层递归逻辑： 对于每个节点，我们要做的就是交换其左右子节点的连接。因此完整的代码如下：
/** // Java
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) return root;
swapChildren(root);
invertTree(root.left);
invertTree(root.right);
return root;
}
private void swapChildren(TreeNode root){
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}
复杂度分析：
时间复杂度：O(n). 因为每个节点被访问一次，然后交换左右节点一次，所以复杂度是O(n)级别。
空间复杂度：O(n)/O(log n). 其实就是O(h)， 取决于树的高度，上一篇文章提过。
题目链接：101. 对称二叉树
状态：第一次没写出来，看解析后做到AC。
看到题目时第一想法：没有什么思路，相比较他们的值吧，好像也不对，想比较节点吧，比较地址好像也不对。没啥想法就看了解析，原来是我想少了，应该就是把每种情况列举清楚就好。那么我们依旧是用递归法来解决这个问题。
依旧是“递归三部曲”：我们要判断的其实是两个子树，所以参数应该是节点的左右两个子树；返回值自然是bool类型。终止条件则是列举出各种情况：左空右不空、或者左不空右空则返回false；左右都空也是对称所以返回true；剩下的情况就是左右都不空了，这种情况下如果节点的值不相等则返回false；再往下运行就说明当前节点的左右子树是对称的了，所以继续调用递归。以下是完整代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution { // Java
public boolean isSymmetric(TreeNode root) {
// recursion
return compare(root.left, root.right);
}
private boolean compare(TreeNode left, TreeNode right){
if(left == null && right != null){
return false;
}
if(left != null && right == null){
return false;
}
if(left == null && right == null){
return true;
}
if(left.val != right.val){
return false;
}
// compare the boundary nodes
boolean compareOutside = compare(left.left, right.right);
// compare the internal nodes
boolean compareInside = compare(left.right, right.left);
return compareOutside && compareInside;
}
}
复杂度分析：
时间复杂度：O(n). 因为每个节点被访问一次，且每次节点被访问的时候都是常量时间的操作，例如检查是否为空，或者比较值是否相等。
空间复杂度：O(n)/O(log n). 仍然是取决于树的高度，同之前说的一样。
题目链接：104. 二叉树的最大深度
状态：一次性AC
看到题目时第一想法：碰巧做到AC，因为其实我没分清深度和高度的区别，我甚至以为深度就是高度，所以碰巧就是求了根到叶子节点的最大距离。
事实上，某节点x的深度是指从根节点到x的最长简单路径的边数。就好比根节点往下生根，要生多长的根才到x呢？这个长度就是节点的深度。某节点y的高度是指y到叶子节点的最长简单路径的边数。就好比叶子节点是0高度，（因为是以叶子节点作为参照物），往上长多少就到了y呢？
而基于二叉树的性质，用前序求深度，后序求高度比较好。因为前序是先处理中间节点，然后往下传值比较方便；而求高度需要先算叶子节点的高度然后再加一才是当前节点的高度，因此得先收集左右子节点的信息然后再处理中间节点，所以由左右中得 后序遍历比较好求高度。以上是大体思路分享，具体完整代码如下：
class Solution { // Java
public int maxDepth(TreeNode root) {
// recursion
if(root == null) return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
看上去很简单是不？其实就是一个后序遍历，而这题求深度之所以也可以用后序遍历就是因为本题求的是最大深度，那实际上就是求根节点的高度，因为最大深度就是根节点的高度。
复杂度分析：
时间复杂度：O(n). 同上，每个节点都访问了，每次访问都是常数级操作
空间复杂度：O(n)/O(log n). 同上，取决于树高h，即树的形状
题目链接：111. 二叉树的最小深度
状态：一次性AC
看到题目时第一想法：和最大深度类似，只不过是在 求左右子树最小值然后加一 之前 序要判断一下是否左右子树为空的情况，如果为空，则应该取另一边。完整代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution { //Java
public int minDepth(TreeNode root) {
// recursion
if(root == null) return 0;
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if(root.left == null){
return rightDepth + 1;
}
if(root.right == null){
return leftDepth + 1;
}
// Neither root.left nor root.right is null;
return Math.min(leftDepth, rightDepth) + 1;
}
}
复杂度分析与前几题完全一样。
