代码随想录算法训练营day 13-14：二叉树初步，递归

（递归遍历和层序遍历比较简单，这里就不写了）

非递归遍历（逻辑的统一与非统一）

逻辑非统一遍历

前序：先右后左入栈

中序：一路向左 + 回溯

后序：最难，需要控制访问顺序（当然，如果用前序的逻辑，最后把结果集反转，要简单很多）

逻辑统一遍历

我们发现，上面的三种遍历，逻辑都不太一样，能不能把逻辑统一一下，只背一个模板呢？

这就需要我们模拟递归的函数栈

栈里放TreeNode，在当前节点入栈后，同时入栈一个 null 当作标记：

第一次遇到节点：先不输出，先安排好它将来的输出时机（null标记）

当从栈里弹出null时：说明下一个弹出的节点就是“该输出”的节点

入栈顺序和遍历顺序反着来即可，前序是根左右，那入栈顺序就是右左根，以此类推

习题思考

LeetCode 226.翻转二叉树

这一题比较简单，先反转再递归还是先递归再反转都行，先反转的逻辑比较直观清晰。

LeetCode 101.对称二叉树

注意该题递归时，左节点和右节点比较完毕以后，应该再比较的是：（左节点左子树，右节点右子树），（左节点右子树，右节点左子树），注意对称比较即可。

LeetCode 104.二叉树最大深度 / 111.二叉树最小深度

最大深度：递归遇到null就返回0，否则沿着左右子树继续往下走，取二者的max再加一，返回值即可，比较简单，也比较好理解。代码如下：

public int maxDepth(TreeNode root) { if(root == null) return 0; int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); return Math.max(leftDepth,rightDepth) + 1; }

最小深度：最初可能会以为，把Math.max改成Math.min不就行了？

还真不行，这两题的隐含条件其实是不一样的，关键点在于：左右子树即使有一边是null的，也不影响“最大”这个概念，但是“最小”就不一样了。

最小深度隐含要求：路径必须走到叶子节点，而 null 不是一条合法的路径，不能把null作为一个路径计数，然后return 0进行高度比较，因为你可能还没走到叶子节点。

随便举一个例子：只含2个节点的树，如果按最大深度的逻辑写最小深度，答案会是1，因为空子树高度是0。但正确答案应该是2，因为你应该比较叶子到根的路径

一句话总结差异：

最大深度：null 是高度为 0 的节点

最小深度：null 是不可通行的方向

这里也把最小深度代码贴出来，可以对比差异：

public int minDepth(TreeNode root) { if(root == null) return 0; if(root.left == null && root.right == null) return 1; if(root.left == null) return minDepth(root.right) + 1; if(root.right == null) return minDepth(root.left) + 1; return Math.min(minDepth(root.left),minDepth(root.right)) + 1; }