leetcode-explore-learn-數據結構-二叉樹2

• 1.概述
• 2.自頂向下/自底向上 框架思想
• 3.例題
• • 3.1對稱二叉樹
  • 3.2路徑總和

本系列博文為leetcode-explore-learn子欄目學習筆記，如有不詳之處，請參考leetcode官網：https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/7/

所有例題的編程語言為python
二叉樹節點結構：

class TreeNode(object):def __init__(self, x):self.val = xself.left = Noneself.right = None

1.概述

樹結構本身是遞歸定義的：一個節點，包含一個值和一個指向其他節點的列表。樹的許多問題可以通過遞歸的方式來解決。對于每一個遞歸層級，我們只需要關注單個節點內的問題，然后通過遞歸調用來解決其子節點問題。

通常通過自頂向上或者自底向上的遞歸來解決樹的問題

遞歸解題，需要存在遞歸函數和原函數，原函數中開啟遞歸入口，遞歸函數不斷遞歸求解。

2.自頂向下/自底向上 框架思想

一道題帶你理解什么是自頂向上/自底向上–二叉樹的最大深度

自頂向下 ：在每個遞歸層級上，先訪問節點來計算一些值，并在遞歸調用時將這些值傳遞給子節點。自頂向下的方案可以看作是一種先序遍歷

根節點的深度是1，對于一個節點其深度為x,那么我們將知道其子節點的深度。在遞歸調用時自頂向下的將節點的深度傳遞為一個參數，那么每一個節點都知道自己的深度，對于葉子節點，可以通過比較確定需不需要更新更大的深度。

class Solution(object):def __init__(self):self.res=0def maxDepth(self, root):""":type root: TreeNode:rtype: int"""def dfs_top_down(node,l):if node==None: # root 本身就是一個空指針returnif node.left==None and node.right==None:self.res=max(self.res,l) # 用max 需要重新定義一個全局變量dfs_top_down(node.left,l+1)dfs_top_down(node.right,l+1)dfs_top_down(root,1)return self.res

自底向上：在每個遞歸層級上，對所有的節點遞歸調用函數，然后根據返回值和根節點本身的值得到答案。自底向上的方案可以看作后序遍歷

如果知道一個根節點，以其左子節點為根的最大深度為l，以其右子節點為根的最大深度為如，那么這個根節點所在子樹的最大深度為$max(l,r)+1$（對于每個節點的答案，都可以在解決它的子節點問題的大難之后得到答案）

class Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""def dfs_bottom_up(node):if node==None:return 0left_l=dfs_bottom_up(node.left)right_l=dfs_bottom_up(node.right)return max(left_l,right_l)+1res=dfs_bottom_up(root)return res

樹遞歸框架的思路：
自頂向上：需要使用一些參數和節點本身的值來決定傳遞給子節點參數
自底向上：如果知道子節點的答案就能知道該節點的答案，采用自底向上是個不錯的選擇

3.例題

3.1對稱二叉樹

給定一個二叉樹，檢查它是否為鏡像對稱
思考失敗，筆記見編輯狀態

核心是驗證root 子樹和root子樹是不是鏡面對稱的。如果是的話，單獨的一棵root樹是鏡面對稱的。
官方求解思路遞歸參考：
如果一個樹的左子樹與右子樹是鏡像對稱的，那么這顆樹也是對稱的。
問題轉換為：兩個子樹在什么情況下對稱
1.跟節點具有相同的值
2.每個樹的右子樹與另一個數的左子樹對稱

class Solution(object):def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""def ismirror_bottom_up(node1,node2):if node1==None and node2==None:return Trueif node1==None or node2==None:return Falsereturn node1.val==node2.val and ismirror_bottom_up(node1.left,node2.right) and ismirror_bottom_up(node1.right,node2.left)flag=ismirror_bottom_up(root,root) # root 和root為鏡像，root自己本身為鏡像return flag

迭代的解法：隊列初始化為[root,root]，將需要比較的點放在相鄰位置。每次彈出兩個節點，如果兩個節點相同時，node1.left 和node2.right 放入隊列；將node1.right與node2.left放入隊列。這樣押入彈出直至對比完該對比的節點。

class Solution(object):def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""que=[root,root]while(que):node1=que.pop(0)node2=que.pop(0)if node1==None and node2==None:continueif node1==None or node2==None:return Falseif node1.val!=node2.val:return Falseque.append(node1.left)que.append(node2.right)que.append(node1.right)que.append(node2.left)return True

3.2路徑總和

給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目標和。

直覺上至頂向下，是可行的思路。在每個節點處將目標值-節點值，將這個差值傳給下一個節點，不斷重復，如果葉子節點處剛好減為0，說明存在一條路徑使得該路徑上所有節點的值相加等于目標和。遞歸函數應該返回True 或者False 程序實現上可以遍歷所有的路徑，將所有的結果取或，但是只有一個為True 其實遞歸就可以終止，這個該怎么寫。

class Solution(object):def hasPathSum(self, root, sum):""":type root: TreeNode:type sum: int:rtype: bool"""def has_top_down(node,target):if node==None:return Falseif node.left==None and node.right==None:if target-node.val==0:return Trueif has_top_down(node.left,target-node.val):return Trueif has_top_down(node.right,target-node.val):return Truereturn Falsereturn has_top_down(root,sum)

維護一個堆棧，用于儲存每一個節點和其需要匹配的信息。每次從堆棧中彈出一個節點，判斷該節點是否為葉子節點，如果為葉子節點，則判斷對應的目標值-節點值是否為0；如果該節點不為葉子節點，將其子節點和相應的信息押入堆棧中。–堆棧如此維護：深度優先遍歷的結構，遍歷完一條路徑之后再去遍歷其他的路徑。第一條走過的是最右邊的路徑，是一個由右往左掃描的過程。

class Solution(object):def hasPathSum(self, root, sum):""":type root: TreeNode:type sum: int:rtype: bool"""if root==None:return Falsestack=[(root,sum)]while(stack):node,target=stack.pop()if node.left==None and node.right==None and node.val-target==0:return Trueif node.left:stack.append((node.left,target-node.val))if node.right:stack.append((node.right,target-node.val))return False 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的算法(15)-leetcode-explore-learn-数据结构-运用递归解决二叉树的问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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