簡介

很多二叉樹的題其實都可以通過遞歸來解決，這些以遞歸解決二叉樹這種對稱數據結構的策略，稱為對稱性遞歸（symmetric recursion）。

對稱性遞歸

對稱性遞歸，指的是對一個對稱的數據結構（典型的是二叉樹）從整體對稱性思考，將大問題分解為多個小問題，即同時考慮對稱的兩部分而不是先解決一部分。

不過，可以通過對稱性遞歸解決的問題主要是判斷性問題，也就是返回值為bool型的，這種求解類型比較適合遞歸函數的調用（單值傳遞）。這類題目一般有兩種情況，一種是單樹問題，一種是雙樹問題。前者不需要用到子樹的某一部分（如根節點左子樹的右子樹），只需要利用根節點左右子樹的對稱性即可進行遞歸；后者則是題目本身要求比較兩棵樹，需要兩棵樹進行判斷。

解題模板

二叉樹對稱性遞歸的解題模板如下，分為遞歸邊界和返回值兩部分。

1.首先是遞歸邊界，也就是特殊情況的判斷。
若是單樹問題，那么一般如下判斷。

if not root: return True/False if not root.left: return True/False/遞歸函數調用 if not root.right: return True/False/遞歸函數調用

若是雙樹問題，那么一般如下判斷。

if not p and not q: return True/False if not p or not q return True/False

當然，有時候也需要加上節點值的判斷。

2.然后就是返回值，通常對稱性遞歸的返回值是多個判斷條件組成的復合語句，通常是下面集中判斷的組合。

• 節點非空的判斷
• 節點值比較的判斷
• （單樹）調用根節點左右子樹的遞歸函數的判斷
• （雙樹）調用兩顆樹的左右子樹的遞歸函數的判斷

題目列表

下面是力扣主站題庫里可以通過上述解法解題的題目目錄。

• leetcode-100 相同的樹
• leetcode-104 二叉樹的最大深度
• leetcode-110 平衡二叉樹
• leetcode-226 翻轉二叉樹
• leetcode-543 二叉樹的直徑
• leetcode-572 另一棵樹的子樹
• leetcode-617 合并二叉樹
• leetcode-965 單值二叉樹

題解列表

100-相同的樹

原題鏈接

這道題要求判斷兩棵二叉樹是否相同。

邊界情況：兩棵樹都是空樹那么必然相同；
返回值：兩棵樹都非空、根節點值相等、左子樹相同、右子樹相同。

Python代碼如下。

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

104-二叉樹的最大深度

原題鏈接

這道題要求求一棵二叉樹的最大深度。

邊界情況：空樹的最大深度為0；
返回值：若樹非空，則最大深度為左子樹最大深度和右子樹最大深度的較大者加上1。

Python代碼如下。

class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0else:return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

110-平衡二叉樹

原題鏈接

這道題要求判斷一棵樹是不是平衡二叉樹（任一節點左右子樹高度差不超過1）。

邊界情況：空樹是平衡二叉樹；
返回值：根的左右子樹高度差不大于1、左右子樹均是平衡二叉樹。

Python代碼如下，計算樹深度的代碼同上一題。

class Solution:def isBalanced(self, root: TreeNode) -> bool:def height(root):if not root:return 0else:return max(height(root.left), height(root.right)) + 1if not root:return Trueelse:return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

226-翻轉二叉樹

原題鏈接

這道題要求將一棵二叉樹鏡像翻轉。

邊界情況：空樹的翻轉是本身；
返回值：翻轉左子樹后替換右子樹，翻轉右子樹替換左子樹。

Python代碼如下。

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

543-二叉樹的直徑

原題鏈接

這題要求一棵二叉樹的直徑。（一棵二叉樹的直徑長度是任意兩個結點路徑長度中的最大值。這條路徑可能穿過也可能不穿過根結點。）

邊界情況：空樹的最大深度為0；
返回值：若樹非空，則最大深度為左子樹最大深度和右子樹最大深度的較大者加上1。

一棵樹的直徑就是對每個節點進行判斷，找到以該節點為起點向左右子樹走經過的節點數，記為$d_{node}=l+r+1$。所有節點中最大的$d_{node}$減去1即為直徑。

Python代碼如下。

class Solution:def diameterOfBinaryTree(self, root: TreeNode) -> int:self.rst = 0def depth(root):if not root:return 0else:l, r = depth(root.left), depth(root.right)self.rst = max(l + r + 1, self.rst)return max(l, r) + 1depth(root)return self.rst - 1

572-另一棵樹的子樹

原題鏈接

這道題要求判斷另一棵樹是不是一棵樹的子樹。

邊界情況：若兩樹中有一者為空則不會存在子樹；
返回值：若兩棵樹不為空，先判斷是不是同一棵樹，同一棵樹就返回True；接著判斷一棵樹的左子樹是否是另一棵樹或者一棵樹的右子樹是否是另一棵樹的子樹。

Python代碼如下，這里求解是否同一棵樹用到了之前的代碼。

class Solution:def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:def isSameTree(p, q):if not p and not q:return Truereturn bool((p and q) and (p.val == q.val) and isSameTree(p.left, q.left) and isSameTree(p.right, q.right))if not root or not subRoot:return Falseif isSameTree(root, subRoot):return Truereturn self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

617-合并二叉樹

原題鏈接

這題要求合并兩個二叉樹，對應位置數值相加。

邊界情況：兩棵樹都為空則返回空樹；其中任意一棵樹為空，返回另一棵樹。
返回值：兩棵樹都不空，則合并后的樹節點值為兩棵樹節點值相加，合并后的左子樹為兩樹的左子樹合并的結果，右子樹也類似。

Python代碼如下。

class Solution:def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:if not root1:return root2if not root2:return root1if root1 and root2:root1.val = root1.val + root2.valroot1.left = self.mergeTrees(root1.left, root2.left)root1.right = self.mergeTrees(root1.right, root2.right)return root1

965-單值二叉樹

原題鏈接

這道題要求判斷一棵樹是不是單值二叉樹（每個節點值相同）。

邊界情況：空樹肯定是單值二叉樹；如果左子樹非空且左子樹根節點值和當前節點值不等則返回False，右子樹類似；
返回值：左子樹是單值二叉樹且右子樹也是單值二叉樹。

Python代碼如下。

class Solution:def isUnivalTree(self, root: TreeNode) -> bool:if not root:return Trueif (root.left and root.left.val != root.val) or (root.right and root.right.val != root.val):return Falsereturn self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

補充說明

本文啟發自一篇力扣題解，簡單以力扣主站題庫為例介紹了比較簡約的對稱性遞歸在實際解題的使用條件和使用方法。

總結

以上是生活随笔為你收集整理的算法模板-对称性递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。