备战蓝桥杯————二叉树解题思维1

小小程序员

发布于 2024-02-26 08:44:49

2950

解决二叉树问题时，常采用两种思维模式：

遍历思维模式： 这种思维模式强调是否可以通过一次遍历二叉树来得到答案。通常使用一个遍历函数（比如前序、中序、后序遍历）结合外部变量来实现。这种方法适用于需要在每个节点上执行相同操作的情况。
分解问题思维模式： 这种思维模式强调是否可以通过定义递归函数，从子问题（子树）的答案推导出原问题的答案。在这种模式下，你需要考虑如何定义递归函数以及如何利用其返回值。通过不断地分解子问题，最终解决整个问题。

不论使用哪种思维模式，都要思考每个单独的二叉树节点需要做什么以及何时做（前序、中序、后序位置）。在递归函数中，你只需关注当前节点，而不必操心其他节点，因为递归会在所有节点上执行相同的操作。二叉树算法的重要性不言而喻。例如，快速排序和归并排序，两种经典排序算法，实际上可以看作是二叉树的前序遍历和后序遍历。对于这两种排序算法，我们可以将其理解为对二叉树节点的特殊处理：前序位置在进入节点时执行，后序位置在离开节点时执行，中序位置在左子树遍历完后、即将开始遍历右子树时执行。这种理解将帮助你深入理解这些高级算法，甚至能够将二叉树的思维应用到动态规划、回溯算法、分治算法和图论算法等其他领域。

一、二叉树的最大深度

题目描述

给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100

解题思路及代码

一棵二叉树的最大深度可以通过子树的最大深度推导出来，这是分解问题计算答案的思路。

/**
 * 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 maxDepth(TreeNode root) {
        if(root==null)return 0;
        int left=0,right=0;
        if(root.left!=null)left=maxDepth(root.left);
        if(root.right!=null)right=maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

结果展示

二、删除有序数组的重复项

题目描述

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

解题思路及代码

/**
 * 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 List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res=new LinkedList<>();
        if(root==null)return res;
        res.add(root.val);
        if(root.left!=null)res.addAll(preorderTraversal(root.left));
        if(root.right!=null)res.addAll(preorderTraversal(root.right));
        return res;
    }
}