?LeetCode刷題實(shí)戰(zhàn)110：平衡二叉樹(shù)
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
我們也可以通過(guò)前序遍歷的方式去更新節(jié)點(diǎn)的深度。但是這里的問(wèn)題和之前的Leetcode 144:二叉樹(shù)的前序遍歷中有一些區(qū)別，之前的問(wèn)題中是輸出節(jié)點(diǎn)，而我們這里是要更新節(jié)點(diǎn)。所以我們不能直接將節(jié)點(diǎn)彈出，而是要保留到更新完節(jié)點(diǎn)后再?gòu)棾觥＿@要怎么做呢？我們可以通過(guò)建立一個(gè)tuple包含一個(gè)seen信息，表示這個(gè)節(jié)點(diǎn)之前是不是訪問(wèn)過(guò)。如果訪問(wèn)過(guò)我們?cè)賹⒐?jié)點(diǎn)彈出，否則的話再將節(jié)點(diǎn)插回去。
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
更多推文：
LeetCode1-100題匯總，希望對(duì)你有點(diǎn)幫助！
LeetCode刷題實(shí)戰(zhàn)101：對(duì)稱(chēng)二叉樹(shù)
LeetCode刷題實(shí)戰(zhàn)102：二叉樹(shù)的層序遍歷
LeetCode刷題實(shí)戰(zhàn)103：二叉樹(shù)的鋸齒形層次遍歷
LeetCode刷題實(shí)戰(zhàn)104：二叉樹(shù)的最大深度
LeetCode刷題實(shí)戰(zhàn)105：從前序與中序遍歷序列構(gòu)造二叉樹(shù)