• 【小嘟陪你刷题15】左叶子之和、二叉树右下角值、路径之和、最大二叉树

    目录

    一、左叶子之和

    在这里插入图片描述

    思路一：递归法

    在做这道题时，我们会想到使用递归的方法来做！
    做了这么多二叉树的题，相信大家已经知道这种题的思路了！先去考虑用什么遍历方法！
    那么我们就可以开始去实现了！
    首先，考虑终止条件：

    if (root == null) return 0;

    • 1

    然后我们去确定单层递归的逻辑当遇到左叶⼦节点的时候，记录数值，然后通过递归求取左⼦树左叶⼦之和，和 右⼦树左叶⼦之和，相加便是整个树的左叶⼦之和。

    代码实现

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {

        if (root == null) return 0;
        if (root.left == null && root.right == null) return 0;
        
        int leftNum = sumOfLeftLeaves(root.left);
        if (root.left != null && root.left.left == null && root.left.right == null) {
            leftNum = root.left.val;
        }
        int rightNum = sumOfLeftLeaves(root.right);
        int sum = leftNum + rightNum;
        return sum;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    在这里插入图片描述

    思路二：迭代法

    迭代法使⽤前中后序都是可以的，只要把左叶⼦节点统计出来，就可以了。
    判断条件是一样的！

    代码实现

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return 0;
        queue.offer(root);
        int sum = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                if (isLeafNode(node.left)) {
                    sum += node.left.val;
                } else {
                    queue.offer(node.left);
                }
            } 
            if (node.right != null) {
                if (!isLeafNode(node.right)) {
                    queue.offer(node.right);
                }
            }
        }
        return sum;
        
    }
    
    public boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    在这里插入图片描述

    二、二叉树右下角值

    在这里插入图片描述

    思路一：递归法

    首先，我们需要理解题目，这道题并不是求最左边的节点，而是深度最大那一层靠最左边的节点，如下图
    在这里插入图片描述
    这道题我们使用什么遍历方式都可以，因为没有中序遍历的逻辑条件！
    确定终止条件
    当遇到叶⼦节点的时候，就需要统计⼀下最⼤的深度了，所以需要遇到叶⼦节点来更新最⼤
    深度。

    if (root == null) {
	return;
}
if (depth > maxDepth) {
	maxDepth = depth;
	result = root.val;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    确定单层递归

    depth++;
dfs(root.left, depth);
dfs(root.right, depth);

    • 1
    • 2
    • 3

    代码实现

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxDepth = 0;
    int result = 0;

    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return result;
    }

    public void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        depth++;
        dfs(root.left, depth);
        dfs(root.right, depth);
        if (depth > maxDepth) {
            maxDepth = depth;
            result = root.val;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    在这里插入图片描述

    思路二：迭代法

    只需要记录最后⼀⾏第⼀个节点的数值就可以了。
    使用层序遍历即可！

    代码实现

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return 0;
        queue.offer(root);
        int result = 0;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur.right != null) {
                queue.offer(cur.right);
            }
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            result = cur.val;
        }
        return result;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    在这里插入图片描述

    三、路径之和

    思路一：递归法

    可以使⽤深度优先遍历的⽅式（本题前中后序都可以，⽆所谓，因为中节点也没有处理逻
    辑）来遍历⼆叉树。
    确定终⽌条件

    if (root == null) return false;

    • 1

    确定单层递归
    如果递归函数返回true，说明找到了合适的路径，应该⽴刻返回。

    if (root.left == null && root.right == null) return targetSum == root.val;

    • 1

    代码实现

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // 终止条件
        if (root == null) return false;
        if (root.left == null && root.right == null) return targetSum == root.val;

        return hasPathSum(root.left, targetSum - root.val)
                || hasPathSum(root.right, targetSum - root.val);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    在这里插入图片描述

    思路二：迭代法

    如果使⽤栈模拟递归的话，那么如果做回溯呢？
    此时栈⾥⼀个元素不仅要记录该节点指针，还要记录从头结点到该节点的路径数值总和。
    这样我们使用两个队列，分别存储将要遍历的节点，以及根节点到这些节点的路径和即可

    代码实现

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();
        queNode.offer(root);
        queVal.offer(root.val);
        while (!queNode.isEmpty()) {
            TreeNode now = queNode.poll();
            int temp = queVal.poll();
            if (now.left == null && now.right == null) {
                if (temp == sum) {
                    return true;
                }
                continue;
            }
            if (now.left != null) {
                queNode.offer(now.left);
                queVal.offer(now.left.val + temp);
            }
            if (now.right != null) {
                queNode.offer(now.right);
                queVal.offer(now.right.val + temp);
            }
        }
        return false;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    在这里插入图片描述

    四、最大二叉树

    在这里插入图片描述

    思路一：递归法

    构造树⼀般采⽤的是前序遍历，因为先构造中间节点，然后递归构造左⼦树和右⼦树。
    确定终止条件
    题⽬中说了输⼊的数组⼤⼩⼀定是⼤于等于1的，所以我们不⽤考虑⼩于1的情况，那么当递
    归遍历的时候，如果传⼊的数组⼤⼩为1，说明遍历到了叶⼦节点了。
    那么应该定义⼀个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表
    ⽰⼀个数组⼤⼩是1的时候，构造了⼀个新的节点，并返回。

    if (rightIndex - leftIndex == 1) {// 只有一个元素
	return new TreeNode(nums[leftIndex]);
}

    • 1
    • 2
    • 3

    确定单层递归

    1. 先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
    int maxIndex = leftIndex;// 最大值所在位置
        int maxVal = nums[maxIndex];// 最大值
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxVal){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    1. 最大值所在的下标左区间 构造左子树，要保证左区间至少有一个数值。
    2. 最大值所在的下标右区间 构造右子树，确保右区间至少有一个数值。

    代码实现

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree1(nums, 0, nums.length);
    }

    public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < 1) {// 没有元素了
            return null;
        }
        if (rightIndex - leftIndex == 1) {// 只有一个元素
            return new TreeNode(nums[leftIndex]);
        }
        int maxIndex = leftIndex;// 最大值所在位置
        int maxVal = nums[maxIndex];// 最大值
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxVal){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        // 根据maxIndex划分左右子树
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    在这里插入图片描述

  • 相关阅读:
    List的介绍
    Jmeter系列(4) 线程属性详解
    PyTorch 2.0 重磅发布：一行代码提速 30%
    数据库Mysql事务，JDBC事务
    密码学之安全模型总结
    String字符串拼接原理
    水环保网关在湿地保护有什么作用？
    jenkins
    MySQL 8.0 新特性之 Clone Plugin
    C++ ：全局变量（extern int a；）、全局函数【可跨文件/模块使用】【只在头文件中做“声明”】
  • 原文地址：https://blog.csdn.net/weixin_61341342/article/details/127577252