1. 遍历问题 Preorder / Inorder / Postorder
preorder: root left right
inorder: left root right
postorder: left right root
遇到二叉树的问题，就是一步步的拆分，最常用的就是Divide & Conquer的递归实现
贴一个preorder的例子
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
""" class Solution:
"""
@param root: The root of binary tree.
@return: Preorder in ArrayList which contains node values.
"""
def preorderTraversal(self, root):
result = []
if root is None:
return result
result = [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
return result
2. 遍历问题的变形，比如Maximum Depth of Binary Tree，是同样的思想，从root出发的最深路径一定是左右子数最深路径的最大值。就可以一步步把树分拆下去。
贴一个代码
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of binary tree.
@return: An integer
"""
def maxDepth(self, root):
depth = 0
if root is None:
return depth
depth = max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
return depth
3. 继续进行延伸，在Balanced binary tree 的做法中可以应用 maxDepth的解法
判断是否是balanced binary tree最直观的就是左右子树的高度差，对任意一个点来说的话 left - right > 1 则不是balanced
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of binary tree.
@return: True if this Binary tree is Balanced, or false.
"""
def maxDepth(self, root):
if root is None:
return 0
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
# at first, the abs is ignored and the operations when the maxdepth is calculated is wrong
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
return max(left, right) + 1 def isBalanced(self, root):
if root is None:
return True
return self.maxDepth(root) != -1