leetcode 二叉树最小深度 最大深度

根节点到叶子节点的距离是深度,没有叶子节点,那么深度是0

求二叉树的最大深度,只需要选择max(leftChildDepth,rightChildDepth)

求二叉树的最短深度,要考虑比较多一点。孩子都不为null 的时候,选择min(leftChildDepth,rightChildDepth),如果有一个孩子是null的,那么选择max(leftChildDepth,rightChildDepth)

Given a binary tree, find its minimum/maximum depth.

The minimum/maximum depth is the number of nodes along
the shortest path from the root node down to the nearest leaf node.

{1,2,3,4,#,#,5}

1
/    \
2         3
/ \       / \
4   #      #    5

 

二叉树最小深度

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepthNums = 0;//minimum depth
    
    public int minDepth(TreeNode root) {
        
            return minNodeDepth(root);
        
    }
    
    int minNodeDepth(TreeNode root){
        if (null == root) return 0;
        
        int rightDep = minNodeDepth(root.right) ;
        int leftDep = minNodeDepth(root.left) ;
        
        if (rightDep!=0 && leftDep!=0)//both nodes are not null, choose min depth
            return Math.min(rightDep, leftDep) + 1;
        else                   // either is null , choose max one,cause the min node is not leaf 
            return Math.max(rightDep, leftDep) + 1;
    }
    
    
}

 

二叉树最大深度

public class Solution {
    public int maxDepthNums = 0;//max depth
    
    public int maxDepth(TreeNode root) {
        
            return maxNodeDepth(root);
        
    }
    
    int maxNodeDepth(TreeNode root){
        if (null == root) return 0;
        
        int rightDep = maxNodeDepth(root.right) ;
        int leftDep = maxNodeDepth(root.left) ;
        
        //if (rightDep!=0 && leftDep!=0)//both nodes are not null, choose max depth
            return Math.max(rightDep, leftDep) + 1;
        //else                   // either is null , choose max one,cause the node is not leaf 
        //    return Math.max(rightDep, leftDep) + 1;
    }
}

 

 

 

Tagged on: , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.