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

小灰灰 2024-04-23 04:05 15阅读 0赞

### 513.找树左下角的值 ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

![43f54f766678f0159d9aea786492f075.png][]

示例 2:

![ff8014daf64cb25938b131ea4a041e58.png][]

4、视频链接：

[怎么找二叉树的左下角？ 递归中又带回溯了，怎么办？| LeetCode：513.找二叉树左下角的值\_哔哩哔哩\_bilibili][_ LeetCode_513._bilibili]

5、思路：

class Solution {
        public int findBottomLeftValue(TreeNode root) {
            private int Deep = -1;
            private int value = 0;
            public int findBottomLeftValue(TreeNode root) {
                value = root.val;
                findLeftValue(root,0);
                return value;
            }
    
            private void findLeftValue (TreeNode root,int deep) {
                if (root == null) return;
                if (root.left == null && root.right == null) {
                    if (deep > Deep) {
                        value = root.val;
                        Deep = deep;
                    }
                }
                if (root.left != null) findLeftValue(root.left,deep + 1);
                if (root.right != null) findLeftValue(root.right,deep + 1);
            }
        }
    }

class Solution {
    
        public int findBottomLeftValue(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int res = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode poll = queue.poll();
                    if (i == 0) {
                        res = poll.val;
                    }
                    if (poll.left != null) {
                        queue.offer(poll.left);
                    }
                    if (poll.right != null) {
                        queue.offer(poll.right);
                    }
                }
            }
            return res;
        }
    }

### 112.路径总和 ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

![29ace9a594893b4d34cb99320537877e.png][]

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2

4、视频链接：

[拿不准的遍历顺序，搞不清的回溯过程，我太难了！ | LeetCode：112. 路径总和\_哔哩哔哩\_bilibili][_ LeetCode_112. _bilibili]

5、思路：

class solution {
       public boolean haspathsum(treenode root, int targetsum) {
            if (root == null) {
                return false;
            }
            targetsum -= root.val;
            // 叶子结点
            if (root.left == null && root.right == null) {
                return targetsum == 0;
            }
            if (root.left != null) {
                boolean left = haspathsum(root.left, targetsum);
                if (left) {      // 已经找到
                    return true;
                }
            }
            if (root.right != null) {
                boolean right = haspathsum(root.right, targetsum);
                if (right) {     // 已经找到
                    return true;
                }
            }
            return false;
        }
    }

class solution {
        public boolean haspathsum(treenode root, int targetsum) {
            if(root == null) return false;
            stack<treenode> stack1 = new stack<>();
            stack<integer> stack2 = new stack<>();
            stack1.push(root);
            stack2.push(root.val);
            while(!stack1.isempty()) {
                int size = stack1.size();
    
                for(int i = 0; i < size; i++) {
                    treenode node = stack1.pop();
                    int sum = stack2.pop();
    
                    // 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
                    if(node.left == null && node.right == null && sum == targetsum) {
                        return true;
                    }
                    // 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
                    if(node.right != null){
                        stack1.push(node.right);
                        stack2.push(sum + node.right.val);
                    }
                    // 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
                    if(node.left != null) {
                        stack1.push(node.left);
                        stack2.push(sum + node.left.val);
                    }
                }
            }
            return false;
        }
    }

### 106.从中序与后序遍历序列构造二叉树 ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 2]

2、文章讲解：[代码随想录][Link 3]

3、题目：

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

*  中序遍历 inorder = \[9,3,15,20,7\]
 *  后序遍历 postorder = \[9,15,7,20,3\] 返回如下的二叉树：

![a22f73137cd8c63987d630223e44e9a1.png][]

4、思路：

class Solution {
        Map<Integer, Integer> map;  // 方便根据数值查找位置
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            map = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
                map.put(inorder[i], i);
            }
    
            return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
        }
    
        public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
            // 参数里的范围都是前闭后开
            if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
                return null;
            }
            int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
            TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
            int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
            root.left = findNode(inorder, inBegin, rootIndex,
                                postorder, postBegin, postBegin + lenOfLeft);
            root.right = findNode(inorder, rootIndex + 1, inEnd,
                                postorder, postBegin + lenOfLeft, postEnd - 1);
    
            return root;
        }
    }

[LeetCode_ -]: https://leetcode.cn/problems/find-bottom-left-tree-value/
[Link 1]: https://www.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
[43f54f766678f0159d9aea786492f075.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/179fb019bb094fb2bd381aac9eb2340a.png
[ff8014daf64cb25938b131ea4a041e58.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/f668e15bd1bc4a4eb3657dd80eca5688.png
[_ LeetCode_513._bilibili]: https://www.bilibili.com/video/BV1424y1Z7pn
[LeetCode_ - 1]: https://leetcode.cn/problems/path-sum/
[Link 2]: https://www.programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[29ace9a594893b4d34cb99320537877e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5aa29ca7ce0b4d428b91ac5df0a5827c.png
[_ LeetCode_112. _bilibili]: https://www.bilibili.com/video/BV19t4y1L7CR
[LeetCode_ - 2]: https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[Link 3]: https://www.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#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[a22f73137cd8c63987d630223e44e9a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/9c7cc3dcdeb54cd4b4ebfbb8a6a27a75.png