面試算法總結：樹、二叉樹、圖
- 1、LeetCode----102. 二叉樹的層次周遊
-
- 基本思路
- 2、LeetCode----235. 二叉搜尋樹的最近公共祖先
-
- 基本思路
- 3、LeetCode----236. 二叉樹的最近公共祖先
-
- 基本思路
- 4、LeetCode----104. 二叉樹的最大深度
-
- Solution1
- Solution2
- 5、LeetCode----111. 二叉樹的最小深度
-
- 基本思路
1、LeetCode----102. 二叉樹的層次周遊
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/submissions/
基本思路
#首先根據題解的含義，需要做的是對二叉樹進行廣度優先的周遊操作。
#但是，從題給的答案我們能看到，題目的要求是我們應該将二叉樹的每一層内容分割開來。
#首先想到的廣度優先周遊，但是每次周遊我們應該再設定一個隊列一個裝此層次的所有節點。
#另外一個隊列裝下一層次的所有節點，每次對每一層的所有節點進行周遊操作。
#周遊完一層之後，我們将下一層的節點複制到本層中再次進行疊代操作。
#外層的循環是一個死循環，想出去的話必須設定break語句
#考慮到節點周遊完成之後存儲周遊值的數組是不會改變内容的，是以加入一個答案檢驗字段進行檢驗，當周遊一次之後答案數列沒有更新則退出周遊。
#依次操作就完成了周遊過程，放回所需的答案。
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
queue = [root]
next_que = []
answer = []
answer_now = []
answer_tem = []
if not root:
return
while 1:
while queue:
node = queue.pop(0)
answer_tem.append(node.val)
if node.left:
next_que.append(node.left)
if node.right:
next_que.append(node.right)
if answer_tem:
answer.append(answer_tem)
answer_tem = []
queue = next_que.copy()
next_que = []
if answer_now == answer:
break
answer_now = answer.copy()
return answer
2、LeetCode----235. 二叉搜尋樹的最近公共祖先
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/submissions/
基本思路
#首先考慮的是二叉搜尋樹的特性，右子樹永遠比根大，左子樹永遠比根小。
#我們通過其特點建構出邏輯，當pq的值都大于根的時候，公共節點肯定在左子樹，反之在右子樹。
#如果全大或者全小都不成立，我們能夠立刻判斷此時通路的節點就是共有根
#注意比較大小的時候沒有等于号，要好好推敲。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if root.val > p.val and root.val > q.val and root.right:
root = root.left
elif root.val < p.val and root.val < q.val and root.left:
root = root.right
else:
return root
3、LeetCode----236. 二叉樹的最近公共祖先
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/submissions/
基本思路
#首先我們想好使用什麼類型的算法，确定使用遞歸算法。
#通過查找左節點和右節點的方式，如果我們要查找的節點在左子樹或者右子樹的節點上找到的話，傳回節點
#并且此節點不為空時也應該傳回此節點以繼續遞歸此節點。否則就傳回空
#當一個節點的子樹找到了p和q那麼此節點為同根節點
#如果隻找到了左子樹，那麼我們傳回右子樹繼續遞歸
#如果隻找到了右子樹，那麼我們傳回左子樹繼續遞歸
#一直進行下去，知道找到左右子樹傳回我們的節點即為最終的共有祖先節點，否則傳回空，無此節點。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
return self.search_node(root, p, q)
def search_node(self, root, p, q):
if not root or root==p or root ==q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
if not left:
return right
if not right:
return left
return None
4、LeetCode----104. 二叉樹的最大深度
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/submissions/
Solution1
#求二叉樹的最大深度，首先想到的是深度優先周遊，構造深度優先周遊算法使用遞歸是很友善的。
#每次進行遞歸查找左右子樹時我們記錄一個level值，并且把目前的值與傳回的lenel1和lenel2比較，取較大的一個。
#遞歸周遊，首先當為根節點時，通路左子樹第一個節點，深度加1，再通路他的左子樹，有則深度加一，沒有則傳回level
#通路完成所有的左根節點時，我們求解到的是左邊的最大深度，進而通路右邊的子樹，最終傳回左右子樹中較大的作為最終的最大深度。
class Solution1:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return self.compute(root, 0)
def compute(self, root, level):
if not root:
return level
level_1 = self.compute(root.left, level+1)
level_2 = self.compute(root.right, level+1)
if level_1 > level:
level = level_1
if level_2 > level:
level = level_2
return level
Solution2
#這也是使用遞歸的算法解決，但比較簡潔，原理是一樣的，每次都遞歸求出左右子樹的最大深度，每次深度加1，（因為每次求左右子樹時深度加了1）
#如此遞歸下去最終傳回的是最大層數
#時間和空間複雜度和上面的代碼是相當的
class Solution2:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
5、LeetCode----111. 二叉樹的最小深度
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/submissions/
基本思路
#與最大深度不同的是，我們應該判斷是否為最小深度，我們隻需判斷此節點是否為葉子結點即可，如果是葉子結點，那麼傳回的深度為1加上上一次計算#的最小深度就是整棵樹的最小深度值
#首先應該保證傳回左子樹和右子樹的最小深度，在保證此條件的基礎上我們還應該判斷：
#如果沒有右子樹，我們則傳回左子樹的最小深度，如果沒有左子樹我們則傳回右子樹的最小深度
#如果沒有左子樹也沒有右子樹，那麼此節點為我們要找的深度節點，傳回1即可，無法将此1加上之前求得的上一次的最小深度則為本二叉樹的最小深度
#如此遞歸下去求得最小葉子結點的層數。
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
if not root.left:
return 1+self.minDepth(root.right)
if not root.right:
return 1+self.minDepth(root.left)
return 1 + min(self.minDepth(root.left), self.minDepth(root.right))