程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Minimum Depth of Binary Tree

LeetCode Minimum Depth of Binary Tree

編輯:關於C++

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
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved