二叉樹中遞歸的思想，在這本Leetbook中講的很細(xì)了，這里不展開。下面是幾道例題：

226. 翻轉(zhuǎn)二叉樹（劍指 Offer 27. 二叉樹的鏡像）

遞歸法前序遍歷：

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:returnroot.left, root.right = root.right, root.left self.invertTree(root.left)self.invertTree(root.right)return root

迭代法前序遍歷：

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return rootstack = []stack.append(root)while stack:node = stack.pop()if node:if node.right:stack.append(node.right)if node.left:stack.append(node.left)stack.append(node)stack.append(None)else:node = stack.pop()node.left, node.right = node.right, node.leftreturn root

遞歸法中序遍歷（偽）：

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:returnself.invertTree(root.left)root.left, root.right = root.right, root.left self.invertTree(root.left)return root

迭代法中序遍歷：

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return rootstack = []stack.append(root)while stack:node = stack.pop()if node:if node.right:stack.append(node.right)stack.append(node)stack.append(None)if node.left:stack.append(node.left)else:node = stack.pop()node.left, node.right = node.right, node.leftreturn root

遞歸法后序遍歷：

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:returnleft = self.invertTree(root.left)right = self.invertTree(root.right)root.left, root.right = right, leftreturn root

迭代法后序遍歷：

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return rootstack = []stack.append(root)while stack:node = stack.pop()if node:stack.append(node)stack.append(None)if node.right:stack.append(node.right)if node.left:stack.append(node.left)else:node = stack.pop()node.left, node.right = node.right, node.leftreturn root

在遍歷的過程中，把記錄節(jié)點(diǎn)值這個(gè)操作改成交換左右子節(jié)點(diǎn)即可，前中后序遍歷都是可以的，遞歸法和迭代法都行。唯一要注意的就是中序遍歷，用遞歸法是左根左，因?yàn)槭褂眠f歸的中序遍歷，某些節(jié)點(diǎn)的左右孩子會(huì)翻轉(zhuǎn)兩次。甚至，層序遍歷也是可以的，可以看我的這篇文章。

100. 相同的樹

class Solution:def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:if (not p) and (not q):return Trueelif (not p) or (not q):return Falseelif p.val != q.val:return Falseelse:return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

判斷兩個(gè)二叉樹是否相同，思路如下：兩個(gè)二叉樹是否同時(shí)為空？是否一個(gè)為空而另一個(gè)不為空？他們的根節(jié)點(diǎn)值是否相同？最后是遞歸的判斷，他們的左右子樹是否都相同？

101. 對(duì)稱二叉樹（劍指 Offer 28. 對(duì)稱的二叉樹）

class Solution:def isSymmetric(self, root: TreeNode) -> bool:return self.check(root, root)def check(self, p: TreeNode, q: TreeNode) -> bool:if (not p) and (not q):return Trueelif (not p) or (not q):return Falseelif p.val != q.val:return Falseelse:return self.check(p.left, q.right) and self.check(p.right, q.left)

判斷一個(gè)二叉樹是否為對(duì)稱二叉樹，可以轉(zhuǎn)化為判斷這個(gè)樹和自己的鏡像樹是否相同。關(guān)鍵在于用 self.check(root, root) 構(gòu)造出兩個(gè)樹，然后以相反方向進(jìn)行遞歸和判斷。

迭代寫法的話使用的是隊(duì)列，用棧或者數(shù)組等其他的容器都行，關(guān)鍵是把節(jié)點(diǎn)放入容器的順序不能錯(cuò)，然后每次取兩個(gè)左右對(duì)應(yīng)位置的節(jié)點(diǎn)出來做比較，如下：

class Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truequeue = collections.deque()queue.append(root.left)queue.append(root.right)while queue:leftNode = queue.popleft()rightNode = queue.popleft()if (not leftNode) and (not rightNode):continueelif (not leftNode) or (not rightNode):return Falseelif leftNode.val != rightNode.val:return Falseelse:queue.append(leftNode.left)queue.append(rightNode.right)queue.append(leftNode.right)queue.append(rightNode.left)return True

617. 合并二叉樹

class Solution:def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:if not root1 and not root2:return Noneif not root1:return root2if not root2:return root1new_root = TreeNode(root1.val + root2.val) # 新建節(jié)點(diǎn)new_root.left = self.mergeTrees(root1.left, root2.left)new_root.right = self.mergeTrees(root1.right, root2.right)return new_root

兩個(gè)二叉樹一起從根節(jié)點(diǎn)開始向下遞歸，如果其中一個(gè)二叉樹的節(jié)點(diǎn)為空，則合并后的節(jié)點(diǎn)就是另一個(gè)二叉樹的節(jié)點(diǎn)。合并后的二叉樹每次都要新建節(jié)點(diǎn)，然后左右子樹用遞歸得到。優(yōu)化的寫法是不新建節(jié)點(diǎn)，直接用其中一個(gè)二叉樹的節(jié)點(diǎn)，只需要把另一個(gè)二叉樹的節(jié)點(diǎn)值加過去即可。

class Solution:def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:if not root1 and not root2:return Noneif not root1:return root2if not root2:return root1root1.val += root2.val # 用舊節(jié)點(diǎn)root1.left = self.mergeTrees(root1.left, root2.left)root1.right = self.mergeTrees(root1.right, root2.right)return root1

104. 二叉樹的最大深度

class Solution:def maxDepth(self, root: TreeNode) -> int:if not root:return 0left_depth = self.maxDepth(root.left)right_depth = self.maxDepth(root.right)return max(left_depth, right_depth) + 1

自底向上的遞歸，在Leetbook中有詳細(xì)介紹，簡(jiǎn)單來說：如果我們知道一個(gè)根節(jié)點(diǎn)，以其左子節(jié)點(diǎn)為根的最大深度為 left_depth 和以其右子節(jié)點(diǎn)為根的最大深度為 right_depth ，我們就可以選擇它們之間的最大值，再加上1來獲得根節(jié)點(diǎn)所在的子樹的最大深度。

543. 二叉樹的直徑

class Solution:def diameterOfBinaryTree(self, root: TreeNode) -> int:self.ans = 1def depth(node: TreeNode):if not node:return 0left_depth = depth(node.left)right_depth = depth(node.right)# 此節(jié)點(diǎn)作為根節(jié)點(diǎn)的最大深度是否為眾節(jié)點(diǎn)中最大，是則更新ansself.ans = max(self.ans, left_depth + right_depth + 1)return max(left_depth, right_depth) + 1depth(root)return self.ans - 1

雖然題目說明了直徑（最大的兩節(jié)點(diǎn)間路徑）不一定經(jīng)過根節(jié)點(diǎn)，但是歸根到底，兩節(jié)點(diǎn)間路徑必然會(huì)有個(gè)根節(jié)點(diǎn)，目標(biāo)就是找到把樹中所有節(jié)點(diǎn)都作為根節(jié)點(diǎn)時(shí)，各自求出最大深度（上一題思路），然后在這些最大深度中找到最大的作為直徑 ans。

563. 二叉樹的坡度

class Solution:def findTilt(self, root: TreeNode) -> int:self.ans = 0def val_sum(node: TreeNode):if not node:return 0left_sum = val_sum(node.left)right_sum = val_sum(node.right)tilt = abs(left_sum - right_sum)self.ans += tiltreturn left_sum + right_sum + node.valval_sum(root)return self.ans

本題與最大深度類似，區(qū)別在于是記錄深度之差的絕對(duì)值（坡度），然后遞歸返回左右子樹和自身值之和。

112. 路徑總和

class Solution:def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:if not root: # 非節(jié)點(diǎn)return Falseif not root.left and not root.right: # 葉子節(jié)點(diǎn)return targetSum == root.valreturn self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

思路是如果子樹的和等于 targetSum 減去當(dāng)前節(jié)點(diǎn)的值，則存在路徑。所以終止條件為非節(jié)點(diǎn)則返回 False，為葉子節(jié)點(diǎn)則返回 targetSum == 當(dāng)前節(jié)點(diǎn)的值，函數(shù)調(diào)用是子節(jié)點(diǎn)和減去當(dāng)前節(jié)點(diǎn)值后的 targetSum 。

113. 路徑總和 II（劍指 Offer 34. 二叉樹中和為某一值的路徑）

class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:ans = []path = []def dfs(root: TreeNode, targetSum: int):if not root:returnpath.append(root.val)targetSum -= root.valif not root.left and not root.right and targetSum == 0:ans.append(path.copy())dfs(root.left, targetSum)dfs(root.right, targetSum)path.pop()dfs(root, targetSum)return ans

這題不是求有沒有路徑，而是要把路徑都找出來，答案放在列表 ans 里。同樣還是遞歸地深度遍歷，用一個(gè) path 列表記錄路徑，如果是葉節(jié)點(diǎn)且和數(shù)符合條件，就往 ans 里面加入路徑 path，否則就遍歷左子樹和右子樹，記得遞歸的最后要把 path 進(jìn)行彈出，然后注意往 ans 里面加入的是 path 的淺拷貝，可以寫成 path.copy() 或者 path[:]

222. 完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)

class Solution:def countNodes(self, root: TreeNode) -> int:if not root:return 0left = root.leftright = root.right# 深度初始化為 0，是因?yàn)槲贿\(yùn)算中 2 << 0 == 2，2 << 1 == 4leftHeight = 0rightHeight = 0# 求左子樹深度while left:left = left.leftleftHeight += 1# 求右子樹深度while right:right = right.rightrightHeight += 1# 若為滿二叉樹，則節(jié)點(diǎn)數(shù)為 2 的 leftHeight 次方，用位運(yùn)算求if leftHeight == rightHeight:return (2 << leftHeight) - 1return self.countNodes(root.left) + self.countNodes(root.right) + 1

這題用常規(guī)的前中后序遍歷或者層序遍歷都能做，但是這樣就沒利用到完全二叉樹的性質(zhì)了。完全二叉樹只有兩種情況，情況一：就是滿二叉樹，情況二：最后一層葉子節(jié)點(diǎn)沒有滿。

對(duì)于情況一，可以直接用 2^樹深度 - 1 來計(jì)算，注意這里根節(jié)點(diǎn)深度為1。

對(duì)于情況二，分別遞歸左孩子，和右孩子，遞歸到某一深度一定會(huì)有左孩子或者右孩子為滿二叉樹，然后依然可以按照情況1來計(jì)算。

優(yōu)化點(diǎn)就是用位運(yùn)算代替指數(shù)運(yùn)算。

236. 二叉樹的最近公共祖先

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':def dfs(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'):# 如果當(dāng)前節(jié)點(diǎn)為空，則說明 p、q 不在 node 的子樹中，不可能為公共祖先，直接返回 Noneif not root:return None# 如果當(dāng)前節(jié)點(diǎn) root 等于 p 或者 q，那么 root 就是 p、q 的最近公共祖先，直接返回 rootif root == p or root == q:return root# 遞歸遍歷左子樹、右子樹，并判斷左右子樹結(jié)果node_left = dfs(root.left, p, q)node_right = dfs(root.right, p, q)# 如果左右子樹都不為空，則說明 p、q 在當(dāng)前根節(jié)點(diǎn)的兩側(cè)，當(dāng)前根節(jié)點(diǎn)就是他們的最近公共祖先if node_left and node_right:return rootelif node_left:return node_left:else:return node_rightans = dfs(root, p, q)return ans

簡(jiǎn)單概括，就是基于后序遍歷，從下往上，在找到 p 或者 q 的時(shí)候就返回。這樣當(dāng) p 和 q 在兩邊時(shí)，就會(huì)返回最近公共祖先；當(dāng) p 和 q 在同一條路徑上時(shí)，就會(huì)返回兩者中作為祖先的那個(gè)。

總結(jié)

以上是生活随笔為你收集整理的二叉树的几道相似简单递归题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。