?LeetCode刷題實戰(zhàn)110：平衡二叉樹
Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
題意
解題
class?Solution:????????
????def?isBalanced(self, root):
????????"""
????????:type root: TreeNode
????????:rtype: bool
????????"""
????????if?not?root:
????????????return?True
????????def?height(node):
????????????if?not?node:
????????????????return?0
????????????return?max(height(node.left), height(node.right)) + 1
????????if?abs(height(root.left) - height(root.right)) > 1:
????????????return?False
????????return?self.isBalanced(root.left) and?self.isBalanced(root.right)
class?Solution:????????
????def?isBalanced(self, root):
????????"""
????????:type root: TreeNode
????????:rtype: bool
????????"""
????????def?height(node):
????????????if?not?node:
????????????????return?0
????????????left = height(node.left)
????????????right = height(node.right)
????????????if?left == -1?or?right == -1?or?abs(left - right) > 1:
????????????????return?-1
????????????return?max(left, right) + 1
????????
????????return?height(root) != -1
class Solution:
????def isBalanced(self, root):
????????"""
????????:type?root:?TreeNode
????????:rtype: bool
????????"""
????????nodes = [root]
????????for?node in nodes:
????????????if?node:
????????????????nodes.extend([node.left, node.right])
????????depths = {}
????????nodes.reverse()
????????for?node in nodes:
????????????if?node:
????????????????if?abs(depths.get(node.left, 0) - depths.get(node.right, 0)) > 1:
????????????????????return?False
????????????????depths[node] = max(depths.get(node.left, 0), depths.get(node.right, 0)) + 1
????????return?True
我們也可以通過前序遍歷的方式去更新節(jié)點的深度。但是這里的問題和之前的Leetcode 144:二叉樹的前序遍歷中有一些區(qū)別，之前的問題中是輸出節(jié)點，而我們這里是要更新節(jié)點。所以我們不能直接將節(jié)點彈出，而是要保留到更新完節(jié)點后再彈出。這要怎么做呢？我們可以通過建立一個tuple包含一個seen信息，表示這個節(jié)點之前是不是訪問過。如果訪問過我們再將節(jié)點彈出，否則的話再將節(jié)點插回去。
class Solution:
????def isBalanced(self, root):
????????"""
????????:type?root:?TreeNode
????????:rtype: bool
????????"""
????????stack = list()
????????stack.append((root, 0))
????????depths = {}
????????while?stack:
????????????node, seen = stack.pop()
????????????if?node:
????????????????if?not seen:
????????????????????stack.extend([(node, 1), (node.right, 0), (node.left, 0)])
????????????????if?abs(depths.get(node.left,0) - depths.get(node.right,0)) > 1:
????????????????????return?False
????????????????depths[node] = max(depths.get(node.left,0), depths.get(node.right,0)) + 1
????????return?True
更多推文：
LeetCode刷題實戰(zhàn)102：二叉樹的層序遍歷
LeetCode刷題實戰(zhàn)103：二叉樹的鋸齒形層次遍歷
LeetCode刷題實戰(zhàn)104：二叉樹的最大深度
LeetCode刷題實戰(zhàn)105：從前序與中序遍歷序列構(gòu)造二叉樹