Leetcode/各大家 -- 104.111 Maximum/Minimum Depth of Binary Tree

104.111 Maximum(Minimum) Depth of Binary Tree （Recursion）

• Difficulty: Easy

 https://leetcode.com/problems/maximum-depth-of-binary-tree/

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 LinkedIn Uber Apple Yahoo

思路: find the max height of left subtree and right subtree

Complexity: O(N) same as traverse tree

public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)return 0;
        int left = maxDepth(root.left)+1;//traverse left subtree + 1(root)
        int right = maxDepth(root.right)+1;//traverse right subtree + 1(root)
        return left>right?left:right;//use the max height of left subtree and right subtree
    }
}

recursion - version 2 

public int maxDepth(TreeNode root) {
        if(root == null)return 0;
        return 1+Math.max(maxDepth(root.left), maxDepth(root.right));
    }

BFS

complexity: time O(n) space O(n), worst case: all leaves in queue # is n/2

public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)return 0;
        Queue<TreeNode> qu = new LinkedList<TreeNode>();
        int depth = 0;
        qu.add(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            depth++;
            for(int i = 0; i < size; i++){//traveling current level, no need add depth
                TreeNode curr = qu.remove();
                if(curr.left != null) qu.offer(curr.left);
                if(curr.right != null) qu.offer(curr.right);
            }
        }
        return depth;
    }
}

111. Minimum Depth of Binary Tree
recursion. 注意左右之一为空时候要return到非空subtree child depth

public class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)return 0;
        int left = 1+minDepth(root.left);
        int right = 1+minDepth(root.right);
        if(left == 1)return right;//case: left subtree is empty
        if(right == 1)return left;//case: right subtree is empty, eg: [1,2] should return 2 not 1
        return left<right?left:right;//case: return min of left & right subtree
    }
}

BFS 

思路：Return height when meeting first leaf node(node.left&node.right = null)

public int minDepth(TreeNode root) {
        if(root == null)return 0;
        Queue<TreeNode> qu = new LinkedList<TreeNode>();
        int depth = 0;
        qu.add(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            depth++;
            for(int i = 0; i < size; i++){//travelling current level, no need add depth
                TreeNode curr = qu.remove();
                if(curr.left == null && curr.right == null) return depth;//when meeting 1st leaf node
                if(curr.left != null) qu.offer(curr.left);
                if(curr.right != null) qu.offer(curr.right);
            }
        }
        return depth;
    }