二叉树总结

二叉树的度

二叉树遍历返回上一层的两种情况：
空结点返回 if(root==nullptr) return ;
该层语句执行完了，返回上一层继续执行。

在遍历过程中，每个结点就是一棵树，叶子结点是一颗左右都为空的树。

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）。
根节点的高度就是这颗树的最大深度，所以求树的深度才可以使用后序遍历。

二叉树解题思路
首先确定采用哪种遍历方式，先写出对应框架，脑海中要有一颗树，对应的遍历顺序是怎样的，不要一下进入到递归中去，先想象直接到最后一层的执行情况。然后确定终止条件和处理逻辑。
具体来说：
i) 和路径、深度有关题目一般用前序遍历，从上到下，注意回溯 *** 作，终止条件是左右子树都为空，在该条件下完成相应的处理逻辑。
ii) 和高度有关题目一般采用后序遍历，从下到上。

递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点
i) 如果需要搜索整颗二叉树且不用处理递归返回值，递归函数就不要返回值。(113.路径总和2)
ii) 如果需要搜索整颗二叉树且需要处理递归返回值，递归函数就需要返回值。（236. 二叉树的最近公共祖先）
iii) 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（112.路径总和）

C++整型上下限INT_MAX INT_MIN及其运算
C++中常量INT_MAX和INT_MIN分别表示最大、最小整数，定义在头文件limits.h中。