代码随想录算法训练营第16天|二叉树part 04

07-19 1404阅读

513.找树左下角的值

题目链接：513. 找树左下角的值 - 力扣（LeetCode）

（图片来源网络，侵删）

视频链接：代码随想录 (programmercarl.com)

第一想法

既然提示说迭代比递归简单一点，那就是找到到最后一层的第一个节点然后返回。那么怎么确定是最后一层呢？

每层遍历时先标记第一个节点tempNode,设置此层是否为最后一层标记flag = true。如果加入非空节点那么说明还有下层，此层就不是最后一层，flag=false。此层遍历解说后flag=true，那么就返回tempNode。

代码随想录

一直向左遍历不是二叉树的左下角，深度最大的叶子节点一定是最后一行。那么如何求得第一个节点呢？前序：中左右，中序：左中右，后序：左右中。本题没有中节点的处理逻辑，那么三种方式其实都相当于优先遍历左节点。一旦得到了深度最大得叶子节点，那么它一定是最靠近左侧的。

最靠左侧的值未必就是左孩子，只要优先遍历左侧就可以。

如果是层序遍历则不用很麻烦，每层遍历记录第一个节点。所有层遍历完后直接返回这个记录值即可。它一定是最后一层得第一个节点。

代码

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque deque = new LinkedList();
        deque.offer(root);
        int result = 0;
        while (!deque.isEmpty()){
            int size = deque.size();
            for (int i = 0; i maxDepth){
                maxDepth = depth;
                result = root.val;
            }
            return;
        }
        //优先遍历左节点
        if(root.left!=null){
            depth++;
            traversal(root.left,depth);
            depth--;//回溯,深度-1
        }
        //再遍历右节点
        if(root.right!=null){
            depth++;
            traversal(root.right,depth);
            depth--;
        }
        //中间节点是不做处理的。
    }
}

路径总和

题目链接：112. 路径总和 - 力扣（LeetCode） 113. 路径总和 II - 力扣（LeetCode）

文档/视频链接：代码随想录 (programmercarl.com)

代码随想录

返回值是Boolean，在这颗二叉树里只需要找到一条路径符合返回直接返回就可以，没有必要遍历所有的节点。所以一旦到叶子节点发现符合要求后，就一路将true返回直至根节点。

参数：计数器 count，TreeNode node

正向思考是：传入0，每遇到一个节点，就加val，看看是不是与target相等。

反向思考：更简单一些，这里直接传入目标值。遇到一个节点就减val。如果到叶子节点，该数值减为0，那么沿此路的所有节点相加恰好等于target。

终止条件：叶子节点并且count为0，return true。

叶子节点但count不为0，return false。

单层递归逻辑：

以上没有对root做判空。

若左不为空：count减左节点的值，递归遍历左孩子。如果左孩子遍历返回来的值是true，则左方向有符合题目要求的路径，那么就应该将这个true结果继续向上返回。回溯将左方向的值加回来。

若右不为空：

如果都没有返回true，那么最终返回false

代码

//LeetCode112
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){
            if(hasPathSum(root.left,targetSum)) return true;
        }
        if(root.right!=null){
            if (hasPathSum(root.right,targetSum))return true;
        }
        return false;
    }
}

LeetCode113，自己写的有错误，还没找出来原因。

class Solution {
    List result;
    LinkedList path;
    public List pathSum (TreeNode root,int targetSum) {
        result = new LinkedList();
        path = new LinkedList();
        travesal(root, targetSum);
        return result;
    }
    private void travesal(TreeNode root,  int count) {
        if (root == null) return;
        path.offer(root.val);
        count -= root.val;
        if (root.left == null && root.right == null && count == 0) {
            result.add(new LinkedList(path));
        }
        travesal(root.left, count);
        travesal(root.right, count);
        path.removeLast(); // 回溯
    }
}

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

题目链接：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

文档/视频链接：代码随想录 (programmercarl.com)

代码随想录想法

框架：

第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组（顺序别搞反了，一定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组

第六步：递归处理左区间和右区间

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length==0||postorder.length==0)
            return null;
        return buildHelper(inorder,0,inorder.length,postorder,0,postorder.length);
    }
    public TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd) {
        if(postorderStart==postorderEnd)return null;
        int rootValue = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootValue);
        int middleIndex;
        for(middleIndex = inorderStart;middleIndex

VPS购买请点击我