LeetCode解題之Minimum Depth of Binary Tree

原題

求一棵二叉樹的最小高度，即從根節點到最近葉子節點的路徑經過的節點數。

注意點：

例子:

輸入:

    3
   / \
  9  20
    /  \
   15   7
  /
 14

輸出: 2

解題思路

可以通過樹的廣度優先遍歷 Binary Tree Level Order Traversal 來實現，在廣度優先遍歷的過程中，每遍歷一層就高度加一，如果某一個節點是葉子節點，那麼當前的高度就是最小高度。

AC源碼

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        depth, curr_level = 0, [root]
        while curr_level:
            depth += 1
            next_level = []
            for n in curr_level:
                left, right = n.left, n.right
                if left is None and right is None:
                    return depth
                if left:
                    next_level.append(left)
                if right:
                    next_level.append(right)
            curr_level = next_level
        return depth


if __name__ == "__main__":
    None