求解二叉樹問題從遞歸著手
Problem 1
計(jì)算二叉樹的形狀
卡特蘭樹的經(jīng)典應(yīng)用
即給定n個(gè)節(jié)點(diǎn)允蜈，計(jì)算有多少個(gè)不同形狀的二叉樹蒿柳，考慮當(dāng)只有一個(gè)節(jié)點(diǎn)或者沒有節(jié)點(diǎn)時(shí)樹只有1個(gè)形狀，當(dāng)有多個(gè)節(jié)點(diǎn)時(shí)妓蛮，給根節(jié)點(diǎn)分配一個(gè)圾叼，左右兩邊各有不同的分法，以此類推构挤，采用遞歸求解惕鼓，符合卡特蘭數(shù)的表達(dá)，代碼如下：
def count(n):
# root : 1
# left : k [0,n-1]
# right : n - 1 - k
if n == 0:
return 1
sum = 0
for k in range(n):
sum += count(k) * count(n-1-k)
return sum
Problem 2
計(jì)算二叉樹的最近祖先
Leetcode 236
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
思路：
解二叉樹的問題一般都往遞歸方向靠攏矾飞，首先考慮特殊情況若p和q其中之一是根節(jié)點(diǎn)呀邢，或者根節(jié)點(diǎn)不存在的情況，直接返回根節(jié)點(diǎn)微谓；
然后從左右子樹中找最近祖先，根據(jù)左右子樹中查找的情況返回結(jié)果豺型，如下代碼所示：
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if p==root or q==root or root==None:
return root
left=self.lowestCommonAncestor(root.left,p,q)
right=self.lowestCommonAncestor(root.right,p,q)
if left==None and right!=None:
return right
if left!=None and right==None:
return left
if left==None and right==None:
return None
return root
Problem 3驗(yàn)證二叉樹是否為二叉查找樹
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
思路：
鄙人剛開始的想法是遞歸判斷節(jié)點(diǎn)的左子樹的值比根節(jié)點(diǎn)小姻氨，右子樹的值比根節(jié)點(diǎn)大，如此可以保證局部的子樹是二叉查找樹前联，但并不能保證全局的結(jié)果娶眷，于是乎，轉(zhuǎn)用其他方法烁落，二叉查找樹的中序遍歷結(jié)果必然是有序的豌注，如此得到了AC，代碼如下：
ret=[]
stack=[]
while stack or root:
if root:
stack.append(root)
root = root.left
else:
temNode = stack.pop()
ret.append(temNode.val)
root = temNode.right
return all([ret[i] < ret[i+1] for i in range(len(ret)-1)])
補(bǔ)充二叉樹的前序轧铁、中序齿风、后序遍歷是基礎(chǔ)中的基礎(chǔ)，需要熟練掌握救斑。
Probelm4二叉樹的子樹和子結(jié)構(gòu)判斷
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
if A==None or B==None:
return False
elif A.val==B.val:
return A.val==B.val or self.isSubStructure(A.left,B.left) or self.isSubStructure(A.right,B.right)
else:
return self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)
樹的子樹判斷
如果兩個(gè)數(shù)的根節(jié)點(diǎn)相同，判斷兩個(gè)樹是否相等巾陕，否則判斷左右子樹是否是子樹的關(guān)系纪他。
class Solution:
def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
def isEqual(S,T):
if not S and not T:
return True
if S and T:
if S.val!=T.val:
return False
return isEqual(S.left,T.left) and isEqual(S.right,T.right)
else:
return False
if not root:
return False
return isEqual(root,subRoot) or self.isSubtree(root.left,subRoot) or self.isSubtree(root.right,subRoot)
