找树左下角的值
卡哥建议：本地递归偏难，反而迭代简单属于模板题， 两种方法掌握一下
题目链接/文章讲解/视频讲解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html
做题思路：
题目说在树的最后一行找到最左边的值。深度最大的叶子节点一定是最后一行。所以要找深度最大的叶子节点。注意：最左边的值不一定是左叶子节点，如果没有左叶子节点，只有右叶子节点的话，那右叶子节点就是最左边的值。
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
那么如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有 中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。
在找最大深度的时候，递归的过程中依然要使用回溯，左子树找完了，再去右子树找。
迭代法看卡哥文章。
本题代码：
1 class Solution {
2 public:
3 int maxDepth = INT_MIN; //int 的最小值
4 int result;
5 void traversal(TreeNode* root, int depth) {
6 if (root->left == NULL && root->right == NULL) {
7 if (depth > maxDepth) {
8 maxDepth = depth;
9 result = root->val;
10 }
11 return;
12 }
13 if (root->left) {
14 depth++;
15 traversal(root->left, depth);
16 depth--; // 回溯
17 }
18 if (root->right) {
19 depth++;
20 traversal(root->right, depth);
21 depth--; // 回溯
22 }
23 return;
24 }
25 int findBottomLeftValue(TreeNode* root) {
26 traversal(root, 0);
27 return result;
28 }
29 };
路径总和
卡哥建议：本题 又一次设计要回溯的过程，而且回溯的过程隐藏的还挺深，建议先看视频来理解 ，112. 路径总和，和 113. 路径总和ii 一起做了。 优先掌握递归法。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
做题思路：
需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。如果遍历到了叶子节点，count不为0，就是没找到。回溯部分在递归完了，再重新让计数器加回值。
本题代码：
1 class Solution {
2 private:
3 bool traversal(TreeNode* cur, int count) {
4 if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
5 if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
6
7 if (cur->left) { // 左
8 count -= cur->left->val; // 递归，处理节点;
9 if (traversal(cur->left, count)) return true;
10 count += cur->left->val; // 回溯，撤销处理结果
11 }
12 if (cur->right) { // 右
13 count -= cur->right->val; // 递归，处理节点;
14 if (traversal(cur->right, count)) return true;
15 count += cur->right->val; // 回溯，撤销处理结果
16 }
17 return false;
18 }
19
20 public:
21 bool hasPathSum(TreeNode* root, int sum) {
22 if (root == NULL) return false;
23 return traversal(root, sum - root->val);
24 }
25 };
从中序与后序遍历序列构造二叉树
卡哥建议：本题算是比较难的二叉树题目了，大家先看视频来理解。 106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树 一起做，思路一样的
题目链接/文章讲解/视频讲解：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html
做题思路：
这里的思路看卡哥视频和文章吧。
中序：左中右
后序：左右中
本题代码：
1 class Solution {
2 private:
3 TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
4 if (postorder.size() == 0) return NULL;//后序里没有根节点
5
6 // 后序遍历数组最后一个元素，就是当前的中间节点
7 int rootValue = postorder[postorder.size() - 1];
8 TreeNode* root = new TreeNode(rootValue);//得到一个根子节点
9
10 // 叶子节点
11 if (postorder.size() == 1) return root;
12
13 // 找到中序遍历的切割点
14 int delimiterIndex;
15 for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
16 if (inorder[delimiterIndex] == rootValue) break; //从后序得到的根节点，再到中序里找根节点，进行切割
17 }
18
19 // 切割中序数组
20 // 左闭右开区间：[0, delimiterIndex)，切的左边是含有切割点的，右边是不含有切割点的
21 vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
22 // [delimiterIndex + 1, end)
23 vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
24
25 // postorder 舍弃末尾元素
26 postorder.resize(postorder.size() - 1);
27
28 // 切割后序数组
29 // 依然左闭右开，注意这里使用了左中序数组大小作为切割点
30 // [0, leftInorder.size)
31 vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());//这里画图理解吧
32 // [leftInorder.size(), end)
33 vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
34
35 root->left = traversal(leftInorder, leftPostorder);
36 root->right = traversal(rightInorder, rightPostorder);
37
38 return root;
39 }
40 public:
41 TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
42 if (inorder.size() == 0 || postorder.size() == 0) return NULL;
43 return traversal(inorder, postorder);
44 }
45 };