111. Minimum Depth of Binary Tree

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

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.

Thoughts

返回二叉树从root到leaf最短的路径长度。分治，返回子树中深度小的那个并加上当前的边，但当子树有个空时由于没有叶结点，忽略。

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        if (root->left != nullptr && root->right == nullptr) return minDepth(root->left) + 1;
        if (root->right != nullptr && root->left == nullptr) return minDepth(root->right) + 1;
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
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;
    }
}

Analysis

时间复杂度O(n).

Ver.2

iterative版分治. 当是叶节点时, 检查下stack长度, 因为stack存的是当前path.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root, pre = null;
        int min = Integer.MAX_VALUE;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.peek();
            if (node.left == null && node.right == null) {
                min = Math.min(min, stack.size());
            }
            if (node.right != null && node.right != pre) {
                cur = node.right;
                continue;
            }
            cur = null;
            pre = stack.pop();
        }

        return min == Integer.MAX_VALUE ? 0 : min;
    }
}