admin管理员组

文章数量:1034928

【DFS】羌笛何须怨杨柳，春风不度玉门关

1. 计算二叉树中的布尔值

题目链接: 2331. 计算布尔二叉树的值

题目内容:

给你一棵 完整二叉树 的根，这棵树有以下特征：

叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。 非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。 计算 一个节点的值方式如下：

如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。 否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。 返回根节点 root 的布尔运算值。

完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。

叶子节点 是没有孩子的节点。

输入：root = [2,1,3,null,null,0,1] 输出：true 解释：上图展示了计算过程。 AND 与运算节点的值为 False AND True = False 。 OR 运算节点的值为 True OR False = True 。 根节点的值为 True ，所以我们返回 true 。 示例 2：

输入：root = [0] 输出：false 解释：根节点是叶子节点，且值为 false，所以我们返回 false 。

提示：

树中节点数目在 [1, 1000] 之间。 0 <= Node.val <= 3 每个节点的孩子数为 0 或 2 。 叶子节点的值为 0 或 1 。 非叶子节点的值为 2 或 3 。

一. 分析

要想知道根节点的布尔值,就得先求左子树和右子树的布尔值.

二. 写递归代码的具体步骤

1. 大量重复子问题(函数头) boolean dfs(TreeNode root)

2. 只关注某一个子问题 想知道根节点的布尔值,就得先求左子树和右子树的布尔值

3. 递归出口 根据题意, 节点值为0,返回false 节点值为1,返回true.

三. 代码实现

代码语言：javascript代码运行次数：0运行复制
class Solution {
    public boolean evaluateTree(TreeNode root) {
        return dfs(root);
    }
    public boolean dfs(TreeNode root) {
        if(root.val == 0) {
            return false;
        }
        if(root.val == 1) {
            return true;
        }
        boolean left = dfs(root.left);
        boolean right = dfs(root.right);
        return root.val == 2 ? left | right : left & right;
    }
}

2. 求根节点到叶节点数字之和

题目链接: 129. 求根节点到叶节点数字之和

题目内容:

  1. 求根节点到叶节点数字之和 已解答 中等 相关标签 相关企业 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3] 输出：25 解释： 从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此，数字总和 = 12 + 13 = 25

输入：root = [4,9,0,5,1] 输出：1026 解释： 从根到叶子节点路径 4->9->5 代表数字 495 从根到叶子节点路径 4->9->1 代表数字 491 从根到叶子节点路径 4->0 代表数字 40 因此，数字总和 = 495 + 491 + 40 = 1026

提示：

树中节点的数目在范围 [1, 1000] 内 0 <= Node.val <= 9 树的深度不超过 10

一. 分析题意

以上图得1节点为例, 第一: 需要接收来自上一层的49. 第二: 需要往下传递49*10+1=491. 第三: 到达叶子节点,需要将结果返回. 分析出这三点,就不难写出递归代码了.

二. 具体步骤

1. 大量重复子问题->(函数头) 上一层节点×10+根节点传给子节点.直到叶子节点才返回最终结果. int dfs(root,presum). presum记录上一层的值.

2. 某一子问题的工作流程 ①计算当前的值,presum*10+root.val; ②前序遍历递归左子树 ③前序遍历递归右子树

3. 递归出口 当前节点为叶子节点时,返回结果

三. 代码实现

代码语言：javascript代码运行次数：0运行复制
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }
    public int dfs(TreeNode root,int presum) {
        presum = presum*10+root.val;
        if(root.left == null && root.right == null) {
            return presum;
        }
        int ret = 0;
        if(root.left != null) {
            ret += dfs(root.left,presum);
        }
        if(root.right != null) {
            ret += dfs(root.right,presum);
        }
        return ret;
    }
}

总结: 凡是能用递归来解决的二叉树题目, 要么是前序遍历,要么是后序遍历, 还有一部分是中序遍历.大部分题都是这样的,一般可以先尝试前序,再后序,最后中序.

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-24，如有侵权请联系 cloudcommunity@tencent 删除二叉树dfsroot遍历递归

【DFS】羌笛何须怨杨柳，春风不度玉门关

1. 计算二叉树中的布尔值

题目链接: 2331. 计算布尔二叉树的值

题目内容:

给你一棵 完整二叉树 的根，这棵树有以下特征：

叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。 非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。 计算 一个节点的值方式如下：

如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。 否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。 返回根节点 root 的布尔运算值。

完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。

叶子节点 是没有孩子的节点。

输入：root = [2,1,3,null,null,0,1] 输出：true 解释：上图展示了计算过程。 AND 与运算节点的值为 False AND True = False 。 OR 运算节点的值为 True OR False = True 。 根节点的值为 True ，所以我们返回 true 。 示例 2：

输入：root = [0] 输出：false 解释：根节点是叶子节点，且值为 false，所以我们返回 false 。

提示：

树中节点数目在 [1, 1000] 之间。 0 <= Node.val <= 3 每个节点的孩子数为 0 或 2 。 叶子节点的值为 0 或 1 。 非叶子节点的值为 2 或 3 。

一. 分析

要想知道根节点的布尔值,就得先求左子树和右子树的布尔值.

二. 写递归代码的具体步骤

1. 大量重复子问题(函数头) boolean dfs(TreeNode root)

2. 只关注某一个子问题 想知道根节点的布尔值,就得先求左子树和右子树的布尔值

3. 递归出口 根据题意, 节点值为0,返回false 节点值为1,返回true.

三. 代码实现

代码语言：javascript代码运行次数：0运行复制
class Solution {
    public boolean evaluateTree(TreeNode root) {
        return dfs(root);
    }
    public boolean dfs(TreeNode root) {
        if(root.val == 0) {
            return false;
        }
        if(root.val == 1) {
            return true;
        }
        boolean left = dfs(root.left);
        boolean right = dfs(root.right);
        return root.val == 2 ? left | right : left & right;
    }
}

2. 求根节点到叶节点数字之和

题目链接: 129. 求根节点到叶节点数字之和

题目内容:

  1. 求根节点到叶节点数字之和 已解答 中等 相关标签 相关企业 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3] 输出：25 解释： 从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此，数字总和 = 12 + 13 = 25

输入：root = [4,9,0,5,1] 输出：1026 解释： 从根到叶子节点路径 4->9->5 代表数字 495 从根到叶子节点路径 4->9->1 代表数字 491 从根到叶子节点路径 4->0 代表数字 40 因此，数字总和 = 495 + 491 + 40 = 1026

提示：

树中节点的数目在范围 [1, 1000] 内 0 <= Node.val <= 9 树的深度不超过 10

一. 分析题意

以上图得1节点为例, 第一: 需要接收来自上一层的49. 第二: 需要往下传递49*10+1=491. 第三: 到达叶子节点,需要将结果返回. 分析出这三点,就不难写出递归代码了.

二. 具体步骤

1. 大量重复子问题->(函数头) 上一层节点×10+根节点传给子节点.直到叶子节点才返回最终结果. int dfs(root,presum). presum记录上一层的值.

2. 某一子问题的工作流程 ①计算当前的值,presum*10+root.val; ②前序遍历递归左子树 ③前序遍历递归右子树

3. 递归出口 当前节点为叶子节点时,返回结果

三. 代码实现

代码语言：javascript代码运行次数：0运行复制
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }
    public int dfs(TreeNode root,int presum) {
        presum = presum*10+root.val;
        if(root.left == null && root.right == null) {
            return presum;
        }
        int ret = 0;
        if(root.left != null) {
            ret += dfs(root.left,presum);
        }
        if(root.right != null) {
            ret += dfs(root.right,presum);
        }
        return ret;
    }
}

总结: 凡是能用递归来解决的二叉树题目, 要么是前序遍历,要么是后序遍历, 还有一部分是中序遍历.大部分题都是这样的,一般可以先尝试前序,再后序,最后中序.

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-24，如有侵权请联系 cloudcommunity@tencent 删除二叉树dfsroot遍历递归

本文标签： DFS羌笛何须怨杨柳，春风不度玉门关

版权声明：本文标题：【DFS】羌笛何须怨杨柳，春风不度玉门关 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748169009a2263326.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。