leetcode 111.Minimum Depth of Binary Tree

2017-08-02

题意

计算二叉树的最低深度

我的思路

遇到叶子节点，对比计算深度。

我的代码

int min = Integer.MAX_VALUE;
public int minDepth(TreeNode root) {
    if(root==null) return 0;
    helper(root,1);         
    return min;
}
void helper(TreeNode node,int deep){
    if(node==null||deep>min) return ;
    if(node.left==null&&node.right==null){
        if(min>deep)
            min = deep;
        return;
    }
    helper(node.left,deep+1);
    helper(node.right,deep+1);
}

大神代码

递归实现

public class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return (left == 0 || right == 0) ? left + right + 1: Math.min(left,right) + 1;

    }
}

非递归实现（效率很快）

int minDepth(TreeNode* root) {
    if (root == NULL) return 0;
    queue<TreeNode*> Q;
    Q.push(root);
    int i = 0;
    while (!Q.empty()) {
        i++;
        int k = Q.size();
        for (int j=0; j<k; j++) {
            TreeNode* rt = Q.front();
            if (rt->left) Q.push(rt->left);
            if (rt->right) Q.push(rt->right);
            Q.pop();
            if (rt->left==NULL && rt->right==NULL) return i;
        }
    }
    return -1; //For the compiler thing. The code never runs here.
}