算法练习之二叉树的最小深度,路径总和详解编程语言

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

/** 
 * 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; 
    } 
}

/** 
 * 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; 
    } 
}

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

/** 
 * 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); 
    } 
}

/** 
 * 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); 
    } 
}