淺析二叉樹的層次遍歷和最大深度
在講解二叉樹的時候，提到二叉樹的遍歷除了前中后序遍歷，還有層次遍歷。
前中后序這三種遍歷方法以及可以通過遞歸的方式實現了，那么今天就來講講層次遍歷吧!
LeetCode 第 102題：二叉樹的層次遍歷
給你一個二叉樹，請你返回其按 層序遍歷 得到的節點值。(即逐層地，從左到右訪問所有節點)。
- 示例：
- 二叉樹：[3,9,20,null,null,15,7],
- # 3
- # / \
- # 9 20
- # / \
- # 15 7
- 返回其層次遍歷結果：
- [
- [3],
- [9,20],
- [15,7]
- ]
對于這道二叉樹題目，我們要遍歷每一層的每一個節點，可以考慮分別用BFS(廣度優先搜索)和DFS(深度優先搜索)來解決，下面先簡單介紹BFS，后續文章繼續深入。
有兩種通用的遍歷樹的策略：
深度優先搜索算法(英語：Depth-First-Search，簡稱DFS)是一種用于遍歷或搜索樹或圖的算法。沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點的所在邊都己被探尋過，搜索將回溯到發現節點的那條邊的起始節點。
深度優先搜索策略又可以根據根節點、左孩子和右孩子的相對順序被細分為先序遍歷，中序遍歷和后序遍歷。
寬度優先搜索算法(又稱廣度優先搜索 英語：Breadth-First Search, 簡稱BFS )
我們按照高度順序一層一層的訪問整棵樹，高層次的節點將會比低層次的節點先被訪問到，最短路徑問題常用此算法。
本題就是用廣度優先搜索，對二叉樹按照層進行搜索，搜索邏輯如下圖所示：
根據我們熟悉的BFS搜索方法，二叉樹的層次遍歷，關鍵要用到隊列，父結點出，就要判斷子結點是否為空，非空則馬上進入隊列,類似廣度優先queue隊列。
把每個沒有搜索到的點依次放入隊列，然后再彈出隊列的頭部元素作為當前遍歷節點，并進行記錄。接下來對此節點的所有相鄰節點進行搜索，將所有有效且未被訪問過的節點壓入隊列中。
- # Definition for a binary tree node.
- # class TreeNode:
- # def __init__(self, x):
- # self.val = x
- # self.left = None
- # self.right = None
- from collections import deque
- class Solution(object):
- def levelOrder(self, root):
- res = []
- if root is None:
- return res
- q = deque([root])
- res.append([root.val])
- while q:
- size = len(q)
- level = []
- for i in range(size):
- node = q.popleft()
- if node.left != None:
- q.append(node.left)
- level.append(node.left.val)
- if node.right != None:
- q.append(node.right)
- level.append(node.right.val)
- if level:
- res.append(level)
- return res
LeetCode 第 107題：二叉樹的層次遍歷II
給定一個二叉樹，返回其節點值自底向上的層次遍歷。(即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷)
- #給定二叉樹 [3,9,20,null,null,15,7],
- # 3
- # / \
- # 9 20
- # / \
- # 15 7
- # 返回其自底向上的層次遍歷為：
- # [
- # [15,7],
- # [9,20],
- # [3]
- #]
- # Related Topics 樹 廣度優先搜索
和LeetCode 第 102題：二叉樹的層次遍歷完全一樣，就是最后的結果改為return res[::-1]
- class Solution:
- def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
- res = []
- if root is None:
- return res
- q = deque([root])
- res.append([root.val])
- while q:
- size = len(q)
- level = []
- for i in range(size):
- node = q.popleft()
- if node.left != None:
- q.append(node.left)
- level.append(node.left.val)
- if node.right != None:
- q.append(node.right)
- level.append(node.right.val)
- if level:
- res.append(level)
- return res[::-1]
LeetCode 第 104題：二叉樹的最大深度
給定一個二叉樹，找出其最大深度。
- # 二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
- # 說明: 葉子節點是指沒有子節點的節點。
- # 示例：
- #給定二叉樹 [3,9,20,null,null,15,7]，
- # 3
- # / \
- # 9 20
- # / \
- # 15 7
- # 返回它的最大深度 3 。
- # Related Topics 樹 深度優先搜索
看到該題目，首先想到的是使用遞歸來實現，遞歸的基本條件是訪問到根節點(左右子樹為空);遞歸條件是訪問左子樹或右子樹;中間處理邏輯是將子樹深度+1，即為最終深度。
- # class TreeNode:
- # def __init__(self, x):
- # self.val = x
- # self.left = None
- # self.right = None
- class Solution:
- # 簡化的遞歸
- def maxDepth(self, root: TreeNode) -> int:
- if not root:
- return 0
- return max(self.maxDepth(root.left), self.maxDepth(root.right))+1
- def maxDepth(self, root: TreeNode) -> int:
- if not root: return 0
- # 分別得到左右子樹的最大深度
- left = self.maxDepth(root.left)
- right = self.maxDepth(root.right)
- return max(left, right) +1
LeetCode 第 110題：平衡二叉樹
給定一個二叉樹，判斷它是否是高度平衡的二叉樹。
- # 本題中，一棵高度平衡二叉樹定義為：
- # 一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1。
- # 示例 1:
- # 給定二叉樹 [3,9,20,null,null,15,7]
- # 3
- # / \
- # 9 20
- # / \
- # 15 7
- # 返回 true 。
- #示例 2:
- # 給定二叉樹 [1,2,2,3,3,null,null,4,4]
- #
- # 1
- # / \
- # 2 2
- # / \
- # 3 3
- # / \
- # 4 4
- # 返回 false 。
- # Related Topics 樹 深度優先搜索
定義一個獲取當前節點高度的方法, 可以參考上面：求二叉樹的最大深度
左右兩個子樹的高度差的絕對值超過1，則為false
如果當前節點的左右子樹滿足高度差的絕對值不超過1，則需要繼續判斷其左右子樹分別是否是平衡二叉樹。
對于每個節點，左子樹和右子樹都是平衡樹，并且得到左子樹和右子樹的高度，只要高度差小于1，則為true。
- # Definition for a binary tree node.
- # class TreeNode(object):
- # def __init__(self, x):
- # self.val = x
- # self.left = None
- # self.right = None
- class Solution:
- def isBalanced(self, root: TreeNode) -> bool:
- if not root: return True
- return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
- self.isBalanced(root.left) and self.isBalanced(root.right)
- def depth(self, root):
- if not root: return 0
- return max(self.depth(root.left), self.depth(root.right)) +
但是時間復雜度卻是，可以采用DFS(深度優先搜索)
- 對二叉樹做深度優先遍歷DFS，遞歸過程中：
- 終止條件：當DFS越過葉子節點時，返回高度0;
- 返回值：從底至頂，返回以每個節點root為根節點的子樹最大高度(左右子樹中最大的高度值加1 max(left,right) + 1);
- 當我們發現有一例 左/右子樹高度差 > 1 的情況時，代表此樹不是平衡樹，返回-1;
- 當發現不是平衡樹時，后面的高度計算都沒有意義了，因此一路返回-1，避免后續多余計算。
最差情況是對樹做一遍完整DFS，時間復雜度為 O(N)。
- class Solution:
- def isBalanced(self, root: TreeNode) -> bool:
- return self.depth(root) != -1
- def depth(self, root):
- if not root: return 0
- left = self.depth(root.left)
- if left == -1: return -1
- right = self.depth(root.right)
- if right == -1: return -1
- return max(left, right) + 1 if abs(left - right) < 2 else -1
本文已收錄 GitHub https://github.com/MaoliRUNsen/runsenlearnpy100更多的文章
