104. 二叉樹的最大深度

給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。

說明:?葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left,right) + 1

111. 二叉樹的最小深度

給定一個二叉樹，找出其最小深度。

最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

說明：葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left = self.minDepth(root.left)
        right = self.minDepth(root.right)
        if not root.left and root.right:
            return 1+right
        if not root.right and root.left:
            return 1+left
        return min(left,right)+1

?要注意：葉子節(jié)點(diǎn)是指沒有左右子節(jié)點(diǎn)的節(jié)點(diǎn)。那么就不能無腦return min(left,right)+1 因?yàn)槿绻筮吺强沼疫叢皇强漳敲磿苯臃祷?而不是右邊的長度

222. 完全二叉樹的節(jié)點(diǎn)個數(shù)

給你一棵 完全二叉樹 的根節(jié)點(diǎn) root ，求出該樹的節(jié)點(diǎn)個數(shù)。

完全二叉樹 的定義如下：在完全二叉樹中，除了最底層節(jié)點(diǎn)可能沒填滿外，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置。若最底層為第 h 層，則該層包含 1~?2h?個節(jié)點(diǎn)。

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/count-complete-tree-nodes
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

暴力解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        res = []
        queue = deque()
        queue.append(root)
        while queue:
            size = len(queue)
            for i in range(0, size):
                node = queue.popleft()
                res.append(node)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return len(res)

普通二叉樹寫法 遞歸 臥槽比循環(huán)還慢！

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left = self.countNodes(root.left)
        right = self.countNodes(root.right)
        return 1+left+right

完全二叉樹寫法 遞歸?更tm慢了文章來源地址http://www.zghlxwxcb.cn/news/detail-485421.html

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root: 
            return 0
        count = 1
        left = root.left
        right = root.right
        while left and right:
            count +=1
            left = left.left
            right = right.right
        if not left and not right: # 如果同時到底說明是滿二叉樹
            return 2**count-1
        return 1+self.countNodes(root.left)+self.countNodes(root.right)

到了這里，關(guān)于Python版day16的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！