编程总结
本篇参考LeetCode学习 https://leetcode-cn.com/leetbook/read/dfs/euapvg/
树的深度优先遍历
二叉树的深度优先遍历从「根结点」开始，依次 「递归地」 遍历「左子树」的所有结点和「右子树」的所有结点
1. 前序遍历
对于任意一棵子树，先输出根结点，再递归输出左子树的 所有 结点、最后递归输出右子树的 所有 结点。上图前序遍历的结果就是深度优先遍历的结果：[0、1、3、4、7、2、5、8、9、6、10]。
2. 中序遍历
对于任意一棵子树，先递归输出左子树的 所有 结点，然后输出根结点，最后递归输出右子树的 所有 结点。上图中序遍历的结果是：
[3、1、7、4、0、8、5、9、2、10、6]。
3. 后序遍历
对于任意一棵子树，总是先递归输出左子树的 所有 结点，然后递归输出右子树的 所有 结点，最后输出根结点。后序遍历体现的思想是：先必需得到左右子树的结果，才能得到当前子树的结果，这一点在解决一些问题的过程中非常有用。上图后序遍历的结果是：
[3、7、4、1、8、9、5、10、6、2、0]。
104. 二叉树的最大深度
int maxDepth(struct TreeNode *root, int len)
{
if (root == NULL) {
return len;
}
return fmax(maxDepth(root->left, len+1), maxDepth(root->right, len+1));
}
二叉树最大深度就是基本的递归思路的求解， 手法主要是递归下去之后len改如何赋值有点搞不清，这里给出了demo的用例，只要能递归就加+1，最后递归到叶子节点返回len。
手法：利用 “递”
144. 二叉树的前序遍历
void PreOrder(struct TreeNode *root, int *ret, int *retIndex)
{
if (root == NULL) {
return;
}
// 根左右 -- 前序
ret[(*retIndex)++] = root->val;
PreOrder(root->left, ret, retIndex);
PreOrder(root->right, ret, retIndex);
}
// 二叉树前序遍历结果存放在 ret 里，idx由retIndex表示
int *preorderTraversal(struct TreeNode *root, int *returnSize)
{
int retIndex = 0;
int *ret = (int *)malloc(sizeof(int) * 100);
memset(ret, 0, sizeof(int) * 100);
PreOrder(root, ret, &retIndex);
*returnSize = retIndex;
return ret;
}
111. 二叉树的最小深度
手法：利用 “归” ，这里不同于二叉树的深度求解，深度是利用递的性质，本题是先递下去，再归时做了处理。（具体见下面代码注释部分）
int minDepth(struct TreeNode *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
int min_depth = INT_MAX; // 手法2：归上来时，要保证每次函数返回值与min_depth的fmin操作时
// 函数返回值都能保留下来，所以min_depth要设置最大值.
if (root->left != NULL) {
min_depth = fmin(minDepth(root->left), min_depth);
}
if (root->right != NULL) {
min_depth = fmin(minDepth(root->right), min_depth);
}
return min_depth + 1; // 手法1：利用归的特性，先递下去求解到叶子节点的数值，进入到循环终止条件
// 然后每层，逐层归上来时+1.
}
112. 路径总和
bool hasPathSum(struct TreeNode *root, int sum)
{
if (root == NULL) {
return false;
}
// 手法1：找到了叶子节点，题目要求找叶子节点的路径和，此时判断 sum 与 target 是否相等.
if (root->left == NULL && root->right == NULL) {
return sum == root->val;
}
// 手法2：否则，继续递归调用，这个手法很巧妙，这样传值下去，其他路径遍历时，sum会恢复至原值.(并没有真正的减val)
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}