算法练习之二叉树的最小深度,路径总和总结

无情 阅读:324 2021-06-16 22:28:45 评论:0

1.二叉树的最小深度

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例: 
给定二叉树 [3,9,20,null,null,15,7], 
    3 
   / \ 
  9  20 
    /  \ 
   15   7 
返回它的最小深度  2.

java

/** 
 * Definition for a binary tree node. 
 * public class TreeNode { 
 *     int val; 
 *     TreeNode left; 
 *     TreeNode right; 
 *     TreeNode(int x) { val = x; } 
 * } 
 */ 
class Solution { 
    public int minDepth(TreeNode root) { 
         
        if(root==null) return 0; 
        int left = minDepth(root.left); 
        int right = minDepth(root.right); 
        if(left!=0&&right!=0){ 
            return 1+Math.min(left,right); 
        } 
        return 1+left+right; 
    } 
}

php

/** 
 * Definition for a binary tree node. 
 * class TreeNode { 
 *     public $val = null; 
 *     public $left = null; 
 *     public $right = null; 
 *     function __construct($value) { $this->val = $value; } 
 * } 
 */ 
class Solution { 
 
    /** 
     * @param TreeNode $root 
     * @return Integer 
     */ 
    function minDepth($root) { 
        if(empty($root)) return 0; 
        $left = $this->minDepth($root->left); 
        $right = $this->minDepth($root->right); 
        if($left!=0&&$right!=0){ 
            return 1+min($left,$right); 
        } 
        return 1+$left+$right; 
    } 
}

2.路径总和

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

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

示例:  
给定如下二叉树,以及目标和 sum = 225 
             / \ 
            4   8 
           /   / \ 
          11  13  4 
         /  \      \ 
        7    2      1 
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

 java

/** 
 * Definition for a binary tree node. 
 * public class TreeNode { 
 *     int val; 
 *     TreeNode left; 
 *     TreeNode right; 
 *     TreeNode(int x) { val = x; } 
 * } 
 */ 
class Solution { 
    public boolean hasPathSum(TreeNode root, int sum) { 
        if(root==null) return false; 
        if(root.left==null&&root.right==null) 
            return sum-root.val==0; 
        return hasPathSum(root.left, sum-root.val)||hasPathSum(root.right, sum-root.val); 
    } 
}

php

/** 
 * Definition for a binary tree node. 
 * class TreeNode { 
 *     public $val = null; 
 *     public $left = null; 
 *     public $right = null; 
 *     function __construct($value) { $this->val = $value; } 
 * } 
 */ 
class Solution { 
 
    /** 
     * @param TreeNode $root 
     * @param Integer $sum 
     * @return Boolean 
     */ 
    function hasPathSum($root, $sum) { 
        if(empty($root)) return false; 
        if(empty($root->left)&&empty($root->right)) 
            return $sum-$root->val==0; 
        return $this->hasPathSum($root->left, $sum-$root->val)||$this->hasPathSum($root->right, $sum-$root->val); 
    } 
}

标签:java
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

我的关注

搜索
关注我们