My accepted Java solution in O(n) times


  • 4
    A

    The key point of my solution is travel the tree by level order. So I can get the answer by find out the first leaf

    1.Create two queues,nodeQueue for TreeNode,depthQueue for current node's level.

    2.Add root to nodeQueue,and add 1 to depthQueue

    3.Do below steps until find out the first leaf

    a.Give the last element of nodeQueue to node,and give the last element of depthQueue to Depth

    b.If node is a leaf, then return Depth

    c.If node.left!=null then add node.left to the nodeQueue,add Depth+1 to depthQueue.

    d.If node.right!=null then add node.right to the nodeQueue,add Depth+1 to depthQueue.

    I know my description is really hard to understand,cause I'm not a English native speaker.

    Thanks so much for you patience!

    public class Solution {
        public int minDepth(TreeNode root) {
            if(root==null) return 0;
            Queue<TreeNode> nodeQueue=new ArrayDeque<TreeNode>();
            Queue<Integer> depthQueue=new ArrayDeque<Integer>();
            int Depth=0;
            nodeQueue.add(root);
            depthQueue.add(1);
            while(!nodeQueue.isEmpty())
            {
                TreeNode node=nodeQueue.remove();
                Depth=depthQueue.remove();
                if(node.left==null && node.right==null)
                {
                    return Depth;
                }
                if(node.left!=null)
                {
                    nodeQueue.add(node.left);
                    depthQueue.add(Depth+1);
                }
                if(node.right!=null)
                {
                    nodeQueue.add(node.right);
                    depthQueue.add(Depth+1);
                }
            }
            return Depth;
        }
    }

  • 0
    S

    Great idea and it's very clear!


  • 0
    A

    Thanks for you comment! : )


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.