代码随想录算法训练营第十八天| 513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树

找树左下角的值  

     卡哥建议：本地递归偏难，反而迭代简单属于模板题， 两种方法掌握一下 

    题目链接/文章讲解/视频讲解：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 };