111. Minimum Depth of Binary Tree

Link

Given a binary tree, find its minimum depth.

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

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.

Solution

這題要考慮兩個子樹的minDepth根真正minDepth的關係。

目標是將minDepth縮減成兩個子樹minDepth的組合。

首先base case是 node == null，此時 minDepth = 0;

接下來看左子樹的minDepth跟右子樹的minDepth。

若只有左子樹(right == 0 && left != 0)，那應該以左子樹的最短depth為主 + 1，

反之只有右子樹(right != 0 && left == 0)，那應該以右子樹的最短depth為主 + 1

若都有，就以兩個子樹的minDepth的最小的那個 + 1 (Math.min(left, right) + 1)

 public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        int depth = 0;
        if(left == 0 && right != 0) depth = right + 1; // root is not leaf
        else if(left != 0 && right == 0) depth = left + 1; // root is not leaf
        else if (left == 0 && right == 0) depth = 1; //root is leaf
        else if (left != 0 && right != 0) depth = Math.min(left, right) + 1; 
        //root is not leaf, min depth shall be the (mindepth of subtree) + 1
        return depth;
    }

T: O(N) 基本上也是每個node都要判斷一次。