LeetCode112

Stella981
• 阅读 711

非商业,LeetCode链接附上:

https://leetcode-cn.com/problems/path-sum/

进入正题。

题目:

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

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

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

LeetCode112

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

代码实现:

//节点
class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
  
        public TreeNode(int val) {
            this.val = val;
        }
}

//方法一 递归
public boolean hasPathSum(TreeNode root, int sum) {

        if(root == null) {
            return false;
        }
        
        if(root.left == null && root.right == null) {
            return root.val == sum;
        }
        
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
//时间复杂度O(n),空间复杂度:O(H),其中 H 是树的高度。

//方法二 迭代
public boolean hasPathSum(TreeNode root, int sum) {

        if(root == null) {
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<>();
        Queue<Integer> queVal = new LinkedList<>();
        queNode.offer(root);
        queVal.offer(root.val);
        
        while (!queNode.isEmpty()) {
            
            TreeNode node = queNode.poll();
            int temp = queVal.poll();
            
            if(node.left == null && node.right == null) {
                if(sum == temp) {
                    return true;
                }
                continue;
            }
            
            if(node.left != null) {
                queNode.offer(node.left);
                queVal.offer(node.left.val + temp);
            }
            if(node.right != null) {
                queNode.offer(node.right);
                queVal.offer(node.right.val + temp);
            }
        }
        
        return false;
}
//时间复杂度O(n),空间复杂度O(n)

分析:

递归的方法,判断终止条件,并逐渐缩小问题规模;

迭代的方法,初始化一个队列(Queue),记录到每一个节点对应的路径值。

--End

本文同步分享在 博客"黑冰台"(CNBlog)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
3年前
B树与B+树的区别?
1.B树简介B树是一种多路平衡搜索树。它由二叉树变换而来的。定义如下:1.1每个节点最多有m1个关键字1.2根节点最少有1个关键字1.3非根节点至少有m/2个关键字1.4每个节点的关键字都是按照从小到大的顺序排列,每个关键字的左子树中的关键字都小于它,而右子树中所有关键字都大于它。1.5所有的叶子节点都处于同
Stella981 Stella981
3年前
LeetCode(98): 验证二叉搜索树
Medium!题目描述:给定一个二叉树,判断其是否是一个有效的二叉搜索树。一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1:输入:2/\
Stella981 Stella981
3年前
LeetCode(110):平衡二叉树
Easy!题目描述:给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树_每个节点_的左右两个子树的高度差的绝对值不超过1。示例1:给定二叉树 3,9,20,null,null,15,73/\920/
Stella981 Stella981
3年前
LeetCode初级算法之树:98 验证二叉搜索树
01题目信息题目地址:https://leetcodecn.com/problems/validatebinarysearchtree/给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。
Wesley13 Wesley13
3年前
C语言递归之二叉树的最小深度
https://www.cnblogs.com/shichampion/p/12262678.html题目描述给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明: 叶子节点是指没有子节点的节点。示例输入:3,9,20,null,null,15,7
Wesley13 Wesley13
3年前
B
BTreeBTree又叫做B树,和平衡二叉树不同的地方在于B树是多叉树(平衡多路查找树),Oracle和MongoDB的索引技术就是基于B树的数据结构,B树也可以看作是对23查找树的一种扩展。一个m阶的BTree有以下性质1.每个节点最多有m个子节点;2.每个非叶子节点(根节点除外)至少含有m/2个子节点;3.
Wesley13 Wesley13
3年前
98. 验证二叉搜索树
题目描述给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。输入:5/\14 /\ 
Wesley13 Wesley13
3年前
JZ18 二叉树镜像
JZ18二叉树镜像题目操作给定的二叉树,将其变换为源二叉树的镜像。思路先遍历,节点入栈,再依次出栈调换左右节点遍历的过程中调换左右节点代码coding:utf8classTreeNode:def__init__
Stella981 Stella981
3年前
Bzoj4899 记忆的轮廓
B.记忆的轮廓题目描述通往贤者之塔的路上,有许多的危机。我们可以把这个地形看做是一颗树,根节点编号为1,目标节点编号为n,其中1n的简单路径上,编号依次递增,在\1,n\中,一共有n个节点。我们把编号在\1,n\的叫做正确节点,\n1,m\的叫做错误节点。一个叶子,如果是正确节点则为正确叶子,否则称
菜园前端 菜园前端
1年前
什么是二叉树?
原文链接:什么是二叉树?树中每个节点最多只能有两个子节点,在JavaScript中一般都是通过Object来模拟二叉树。常用操作前序遍历中序遍历后序遍历前序遍历根左右。口诀:1.访问根节点2.对根节点的左子树进行前序遍历3.对根节点的右子树进行前序遍历通过