2025/9/15 【二叉樹12】平衡二叉樹

110. 平衡二叉樹 - 力扣（LeetCode）

二叉樹節點的深度：指從根節點到該節點的最長簡單路徑邊的條數。

二叉樹節點的高度：指從該節點到葉子節點的最長簡單路徑邊的條數。

但leetcode中強調的深度和高度很明顯是按照節點來計算的。

求深度適合用前序遍歷，而求高度適合用后序遍歷。

方法一：遞歸

關于根節點的深度究竟是1 還是 0，不同的地方有不一樣的標準，leetcode的題目中都是以節點為一度，即根節點深度是1。但維基百科上定義用邊為一度，即根節點的深度是0。

# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        if self.get_height(root) != -1:
            return True
        else:
            return False

    def get_height(self, root):
        if not root:
            return 0
        if (left_height := self.get_height(root.left)) == -1:
            return -1
        if (right_height := self.get_height(root.right)) == -1:
            return -1
        if abs(left_height - right_height) > 1:
            return -1
        else:
            return 1 + max(left_height, right_height)

方法二：迭代

在104.二叉樹的最大深度中我們可以使用層序遍歷來求深度，但是就不能直接用層序遍歷來求高度了，這就體現出求高度和求深度的不同。

# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        st = []
        st.append(root)
        while st:
            node = st.pop()
            if abs(self.getDepth(node.left) - self.getDepth(node.right)) > 1:
                return False
            if node.right:
                st.append(node.right)
            if node.left:
                st.append(node.left)
        return True

    def getDepth(self, cur):
        if not cur:
            return 0
        
        st = []
        st.append(cur)
        depth = 0
        result = 0
        while st:
            node = st[-1]
            if node is not None:
                st.pop()
                st.append(node)
                st.append(None)
                depth += 1
                if node.right:
                    st.append(node.right)
                if node.left:
                    st.append(node.left)
            else:
                st.pop()
                st.pop()
                depth -= 1
            result = max(result, depth)
        return result

posted on 2025-09-15 15:23 axuu 閱讀(9) 評論(0) 收藏舉報

刷新頁面返回頂部