亚洲日韩欧美一区,日本一本在线观看视频干女人 ,国产女人操逼视屏免费播,欧美一区二区三区四区在线视频 ,欧美黄色操逼,成人夜间视频,尹人网午夜视频,中文字幕色

點擊上方“小白學視覺”，選擇加"星標"或“置頂”

重磅干貨，第一時間送達

1 二叉樹簡介

二叉樹是最基本的數(shù)據(jù)結(jié)構(gòu)之一，二叉樹（Binary Tree）是包含n個節(jié)點的有限集合，該集合或者為空集（此時，二叉樹稱為空樹），或者由一個根節(jié)點和兩棵互不相交的、分別稱為根節(jié)點的左子樹和右子樹的二叉樹組成。

一個典型的二叉樹如下圖所示

由上述的定義可以看出，二叉樹中的節(jié)點至多包含兩棵子樹，分別稱為左子樹和右子樹，而左子樹和右子樹又分別至多包含兩棵子樹。由上述的定義，二叉樹的定義是一種遞歸的定義。

對于二叉樹，包含一些性質(zhì)：

在二叉樹中，第? $i$ ?層上至多有? $2^{i-1}$ ?個節(jié)點? $(i\ge 1)$ ?
深度為的二叉樹至多有? $2^{k-1}$ ?個節(jié)點? $(k\ge 1)$ ?
對一棵二叉樹，如果葉子節(jié)點的個數(shù)為? $n_0$ ?，度為2的節(jié)點個數(shù)為? $n_2$ ?，則? $n_0=n_2+1$ ?
具有? $n$ ?個節(jié)點的完全二叉樹的深度為??+1

2 二叉樹的遍歷

前序遍歷：先訪問根節(jié)點，再前序遍歷左子樹，再前序遍歷右子樹

中序遍歷：先中序遍歷左子樹，再訪問根節(jié)點，再中序遍歷右子樹

后序遍歷：先后序遍歷左子樹，再后序遍歷右子樹，再訪問根節(jié)點

層序遍歷：按二叉樹的深度，一層一層依次遍歷

注意點

以根訪問順序決定是什么遍歷
左子樹都是優(yōu)先右子樹

2.1 遞歸解法

2.1.1 前序遍歷

def preorderTraversal(self, root: TreeNode) -> List[int]:  def dfs(root):    if not root:      return     res.append(root.val) # 將根節(jié)點插入棧中    dfs(root.left)    dfs(root.right)  dfs(root)  return res

2.1.2 中序遍歷

def inorderTraversal(self, root: TreeNode) -> List[int]:  def dfs(root):    if not root:      return     dfs(root.left)    res.append(root.val)  # 將根節(jié)點插入棧中    dfs(root.right)  dfs(root)  return res

2.1.3 后序遍歷

def posorderTraversal(self, root: TreeNode) -> List[int]:  def dfs(root):    if not root:      return     dfs(root.left)    dfs(root.right)    res.append(root.val)  # 將根節(jié)點插入棧中  dfs(root)  return res

一樣的代碼，稍微調(diào)用一下位置就可以，如此固定的套路，使得只掌握遞歸解法并不足以令面試官信服。

因此我們有必要再掌握迭代解法，同時也會加深我們對數(shù)據(jù)結(jié)構(gòu)的理解。

2.2 迭代解法

2.2.1 前序遍歷

144. 二叉樹的前序遍歷

# 常規(guī)解法def preorderTraversal(self, root: TreeNode) -> List[int]:  if root is None:    return []  res = []  stack = [root]  # 輔助棧  while stack:    root = stack.pop()    if root is not None:      res.append(root.val)      if root.right is not None:        stack.append(root.right)      if root.left is not None:        stack.append(root.left)
  return res

# 模版解法def preorderTraversal(self, root: TreeNode) -> List[int]:  res = []  stack = []  # 輔助棧  while stack or root:    while root:      '''      這其實就是在對于每個節(jié)點，遍歷它的左孩子鏈，并且在遍歷的過程中，保存遍歷的結(jié)果,并且在每遍歷一個左節(jié)點的時候，都添加它的右孩子到輔助棧中      '''      res.append(root.val)  # 將根節(jié)點加入列表      stack.append(root)      root = root.left   # 遍歷左子樹    root = stack.pop()   # 左子樹遍歷完畢    root = root.right    # 遍歷右子樹  return res

# 顏色標記法'''使用顏色標記節(jié)點的狀態(tài)，新節(jié)點為白色，已訪問的節(jié)點為灰色。如果遇到的節(jié)點為白色，則將其標記為灰色，然后將其右子節(jié)點、自身、左子節(jié)點依次入棧。如果遇到的節(jié)點為灰色，則將節(jié)點的值輸出。令白色為0，灰色為1'''def preorderTraversal(self, root: TreeNode) -> List[int]:  res = []  stack = [(0, root)]  while stack:    flag, node = stack.pop()    if node is None: continue   # 空結(jié)點跳過    if flag == 0:      # 前序的倒序記錄，子結(jié)點標記為 1，已經(jīng)標過 1 的父結(jié)點狀態(tài)置為 0      stack.append((0, node.right))      stack.append((0, node.left))      stack.append((1, node))     else:  # 標記為1則輸出      res.append(node.val)  return res

2.2.2 中序遍歷

94. 二叉樹的中序遍歷

# 模版解法def inorderTraversal(self, root: TreeNode) -> List[int]:  res = []  stack = []  # 輔助棧  while stack or root:    while root:      stack.append(root)      root = root.left   # 遍歷左子樹    root = stack.pop()   # 左子樹遍歷完畢    res.append(root.val) # 將根節(jié)點加入列表    root = root.right    # 遍歷右子樹  return res

# 顏色標記法def preorderTraversal(self, root: TreeNode) -> List[int]:  res = []  stack = [(0, root)]  while stack:    flag, node = stack.pop()    if node is None: continue   # 空結(jié)點跳過    if flag == 0:      # 前序的中序記錄，子結(jié)點標記為 1，已經(jīng)標過 1 的父結(jié)點狀態(tài)置為 0      stack.append((0, node.right))      stack.append((1, node))       stack.append((0, node.left))    else:  # 標記為1則輸出      res.append(node.val)  return res

2.2.3 后序遍歷

145. 二叉樹的后序遍歷

# 模版解法# 將前序遍歷結(jié)果倒敘輸出def posorderTraversal(self, root: TreeNode) -> List[int]:  res = []  stack = []  # 輔助棧  while stack or root:    while root:      res.append(root.val) # 將根節(jié)點加入列表      stack.append(root)      root = root.left   # 遍歷左子樹    root = stack.pop()   # 左子樹遍歷完畢    root = root.right    # 遍歷右子樹  return res[::-1]

# 顏色標記法def preorderTraversal(self, root: TreeNode) -> List[int]:  res = []  stack = [(0, root)]  while stack:    flag, node = stack.pop()    if node is None: continue   # 空結(jié)點跳過    if flag == 0:      # 后序的中序記錄，子結(jié)點標記為 1，已經(jīng)標過 1 的父結(jié)點狀態(tài)置為 0      stack.append((0, node))       stack.append((0, node.left))      stack.append((1, node.right))    else:  # 標記為1則輸出      res.append(node.val)  return res

2.3 層序遍歷

二叉樹的層次遍歷的迭代方法與前面不用，因為前面的都采用了深度優(yōu)先搜索的方式，而層次遍歷使用了廣度優(yōu)先搜索，廣度優(yōu)先搜索主要使用隊列實現(xiàn)，也就不能使用前面的模板解法了。

廣度優(yōu)先搜索的步驟為：

初始化隊列 q，并將根節(jié)點 root 加入到隊列中；
當隊列不為空時：

隊列中彈出節(jié)點 node，加入到結(jié)果中；
如果左子樹非空，左子樹加入隊列；
如果右子樹非空，右子樹加入隊列；

102. 二叉樹的層序遍歷

# BFSdef levelOrder(self, root: TreeNode) -> List[List[int]]:  if not root:    return []  res = []  queue = [root]
  while queue:    level = []  # 保存每一層的節(jié)點    for _ in range(len(queue)):      node = queue.pop(0)  # 取隊列頭節(jié)點      level.append(node.val)      if node.left:        queue.append(node.left)      if node.right:        queue.append(node.right)
    res.append(level)
  return res

# DFS 使用遞歸調(diào)用DFS，添加一個深度的參數(shù)# 記錄每個節(jié)點的深度 depth。遞歸到新節(jié)點要把該節(jié)點放入 depth 對應列表的末尾def levelOrder(self, root: TreeNode) -> List[List[int]]:  res = []  if not root:    return
  def dfs(node, depth):    if len(res) == depth:      res.append([])  # 當一層遍歷完，添加[]    res[depth].append(node.val) # 將節(jié)點添加進[]末尾    if node.left is not None:      dfs(node.left, depth + 1)     if node.right:      dfs(node.right, depth + 1)
  dfs(root, 0)  return res

107. 二叉樹的層次遍歷 II

給定一個二叉樹，返回其節(jié)點值自底向上的層次遍歷。（即按從葉子節(jié)點所在層到根節(jié)點所在的層，逐層從左向右遍歷）

# BFSdef levelOrder(self, root: TreeNode) -> List[List[int]]:  if not root:    return []  res = []  queue = [root]
  while queue:    level = []  # 保存每一層的節(jié)點    for _ in range(len(queue)):      node = queue.pop(0)  # 取隊列頭節(jié)點      level.append(node.val)      if node.left:        queue.append(node.left)      if node.right:        queue.append(node.right)
    res.insert(0, level)  # 插入到列表開頭
  return res

# DFS 使用遞歸調(diào)用DFS，改用insert插入到列表開頭def levelOrder(self, root: TreeNode) -> List[List[int]]:  res = []  if not root:    return
  def dfs(node, depth):    if len(res) == depth:      res.insert(0, [])  # 當一層遍歷完，插入[]到開頭    res[-(depth+1)].append(node.val) # 將節(jié)點添加進[]    if node.left is not None:      dfs(node.left, depth + 1)     if node.right:      dfs(node.right, depth + 1)
  dfs(root, 0)  return res

3 常見題目示例

104. 二叉樹的最大深度

給定一個二叉樹，找出其最大深度。

思路1：廣度優(yōu)先搜索BFS

思路2：分治法

# BFSdef maxDepth(self, root: TreeNode) -> int:  if root is None:      return 0  queue = [(1, root)]  # 添加一個層數(shù)depth參數(shù)  while queue:      depth, root = queue.pop(0)      if root.left:          queue.append((depth+1, root.left))      if root.right:          queue.append((depth+1, root.right))  return depth

# 分治算法def maxDepth(self, root: TreeNode) -> int:   if root is None:       return 0   left = self.maxDepth(root.left)   right = self.maxDepth(root.right)
   if left > right:       return left + 1   else:       return right + 1

110. 平衡二叉樹

給定一個二叉樹，判斷它是否是高度平衡的二叉樹。
本題中，一棵高度平衡二叉樹定義為：
?一個二叉樹每個節(jié)點?的左右兩個子樹的高度差的絕對值不超過1。

思路：分治法，左邊平衡 && 右邊平衡 && 左右兩邊高度 <= 1，因為需要返回是否平衡及高度，要么返回兩個數(shù)據(jù)，要么合并兩個數(shù)據(jù)，所以用-1 表示不平衡，>0 表示樹高度（二義性：一個變量有兩種含義）。

# 分治法def isBalanced(self, root: TreeNode) -> bool:  def maxDepth(root):    if not root:        return 0    left = maxDepth(root.left)    if left  == -1:        return -1    right = maxDepth(root.right)    if right == -1:        return -1    return max(left, right) + 1 if abs(left - right) < 2 else -1   
  return maxDepth(root) != -1

def isBalanced(self, root: TreeNode) -> bool:  def maxDepth(root):      if not root:          return True, 0      lf, lh = maxDepth(root.left)      rf, rh = maxDepth(root.right)      if lf and rf and abs(lh-rh) < 2:          return True, max(lh, rh) + 1      return False, max(lh, rh) + 1  return maxDepth(root)[0]

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

給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

思路：分治法，有左子樹的公共祖先或者有右子樹的公共祖先，就返回子樹的祖先，否則返回根節(jié)點

當 left 和 right 同時為空：說明 root 的左 / 右子樹中都不包含 p,q ，返回 None ；
當 left 和 right 同時不為空：說明 p, q 分列在 root 的異側(cè) （分別在左 / 右子樹），因此 root 為最近公共祖先，返回 root ；
當 left 為空，right 不為空：p, q都不在 root 的左子樹中，直接返回 right 。具體可分為兩種情況：

3.1 p, q 其中一個在 root 的右子樹中，此時 right 指向 p（假設為 p ）

3.2 p, q 兩節(jié)點都在 root 的右子樹中，此時的 right 指向最近公共祖先節(jié)點

當 left 不為空， right 為空：與情況 3. 同理；

# 左搜搜，右搜搜。左右都有，那就是你；左沒便在右，右沒便在左def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':  if root in (None, p, q):  # 如果不為樹，或者p或q為根節(jié)點，則直接返回根節(jié)點    return root  left = self.lowestCommonAncestor(root.left, p, q)  right = self.lowestCommonAncestor(root.right, p, q)  if left and right:    # 左右節(jié)子樹返回值均不為None    return root  if not left:    # 左沒便在右              return right  if not right:   # 右沒便在左    return left

103. 二叉樹的鋸齒形層次遍歷

給定一個二叉樹，返回其節(jié)點值的鋸齒形層次遍歷。（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行）。

思路：根據(jù)層數(shù)奇偶不同選擇順序或倒序排列，基本方法與層次遍歷一樣，只是遇到奇數(shù)層（層數(shù)從0開始）要倒序插入

def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:    res = []    def helper(root, depth):        if not root:            return        if len(res) == depth:            res.append([])        if depth %2 == 0:  # 偶數(shù)行正常排序            res[depth].append(root.val)        else:              # 奇數(shù)行倒序插入            res[depth].insert(0, root.val)        helper(root.left, depth + 1)        helper(root.right, depth + 1)
    helper(root, 0)    return res

701. 二叉搜索樹中的插入操作

給定二叉搜索樹（BST）的根節(jié)點和要插入樹中的值，將值插入二叉搜索樹。返回插入后二叉搜索樹的根節(jié)點。保證原始二叉搜索樹中不存在新值。
注意，可能存在多種有效的插入方式，只要樹在插入后仍保持為二叉搜索樹即可。你可以返回任意有效的結(jié)果。

思路：找到最后一個葉子節(jié)點滿足插入條件即可

# DFS遞歸查找插入位置def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:   if not root:     # 根節(jié)點為空，則直接插入到根節(jié)點的位置       return TreeNode(val)   # 當root.val > val時，插入到左子樹   if root.val > val:       root.left = self.insertIntoBST(root.left, val)   # 當root.val < val時，插入到右子樹   else:       root.right = self.insertIntoBST(root.right, val)   return root

# 迭代def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:  node = root   # 創(chuàng)建指針指向root  while node:    # 當node.val > val時，插入到左子樹    if node.val > val:      if not node.left:  # 當左子樹沒有左子節(jié)點，則插入到左子樹左子節(jié)點        node.left = TreeNode(val)        return root      else:      # 左子節(jié)點存在，則指針指向左子節(jié)點        node = node.left      else:      if not node.right:        node.right = TreeNode(val)        return root      else:     # 右子節(jié)點存在，則指針指向右子節(jié)點        node = node.right    return TreeNode(val)

98. 驗證二叉搜索樹

給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。

思路 1：中序遍歷，檢查結(jié)果列表是否已經(jīng)有序

思路 2：分治法，判斷左 MAX < 根 < 右 MIN

def isValidBST(self, root: TreeNode) -> bool:   # 中序遍歷   stack = []   temp = float('-inf')   while stack or root:       while root:           stack.append(root)           root = root.left    # 遍歷左子樹       root = stack.pop()      # 左子樹遍歷完成，此時root為左子樹葉子節(jié)點       # 由于節(jié)點遍歷順序是左根右，每次讓當前節(jié)點與上一個保存當節(jié)點值比較，即當前為根節(jié)點，則上一個節(jié)點為左節(jié)點，值當前節(jié)點小于上一個節(jié)點，則返回False       if root.val <= temp:           return False       temp = root.val         # temp值變?yōu)楫斍肮?jié)點當值       root = root.right       # 遍歷右子樹   return True

# 分治法def isValidBST(self, root: TreeNode) -> bool:  def helper(root, lower = float('-inf'), upper = float('inf')):    # 遞歸終止條件，當遞歸到葉子節(jié)點，則退出    if not root:          return True        # 判斷是否在區(qū)間內(nèi)，即判斷左 MAX < 根 < 右 MIN    if root.val <= lower or root.val >= upper:        return False    # 判斷左子樹，上邊界設為根節(jié)點的值    if not helper(root.left, lower, root.val):        return False    # 判斷右子樹，下邊界設為根節(jié)點的值    if not helper(root.right, root.val, upper):        return False    # 前面判斷都沒有返回False的情況，則是平衡樹    return True        
  return helper(root)

124. 二叉樹中的最大路徑和

給定一個非空二叉樹，返回其最大路徑和。
本題中，路徑被定義為一條從樹中任意節(jié)點出發(fā)，達到任意節(jié)點的序列。該路徑至少包含一個節(jié)點，且不一定經(jīng)過根節(jié)點。

思路：分治法，分為三種情況：左子樹最大路徑和最大，右子樹最大路徑和最大，左右子樹最大加根節(jié)點最大，需要保存兩個變量：一個保存子樹最大路徑和，一個保存左右加根節(jié)點和，然后比較這個兩個變量選擇最大值即可

def maxPathSum(self, root: TreeNode) -> int:  self.maxSum = float("-inf")    # 定義全局變量，保存最大和  def maxGain(node):    if not node:        return 0    # 遞歸計算左右子節(jié)點的最大路徑和    left = maxGain(node.left)     right = maxGain(node.right)
    # 節(jié)點的最大路徑和取決于該節(jié)點的值與該節(jié)點的左右子節(jié)點的最大路徑和    total = max(node.val,                node.val + left,                node.val + right)          # 更新最大路徑和    self.maxSum = max(self.maxSum, total, node.val + left + right)     # 返回節(jié)點的最大貢獻值    return total
  maxGain(root)  return self.maxSum

下載1：OpenCV-Contrib擴展模塊中文版教程

在「小白學視覺」公眾號后臺回復：擴展模塊中文教程，即可下載全網(wǎng)第一份OpenCV擴展模塊教程中文版，涵蓋擴展模塊安裝、SFM算法、立體視覺、目標跟蹤、生物視覺、超分辨率處理等二十多章內(nèi)容。

下載2：Python視覺實戰(zhàn)項目52講

在「小白學視覺」公眾號后臺回復：Python視覺實戰(zhàn)項目，即可下載包括圖像分割、口罩檢測、車道線檢測、車輛計數(shù)、添加眼線、車牌識別、字符識別、情緒檢測、文本內(nèi)容提取、面部識別等31個視覺實戰(zhàn)項目，助力快速學校計算機視覺。

下載3：OpenCV實戰(zhàn)項目20講

在「小白學視覺」公眾號后臺回復：OpenCV實戰(zhàn)項目20講，即可下載含有20個基于OpenCV實現(xiàn)20個實戰(zhàn)項目，實現(xiàn)OpenCV學習進階。

交流群

歡迎加入公眾號讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動駕駛、計算攝影、檢測、分割、識別、醫(yī)學影像、GAN、算法競賽等微信群（以后會逐漸細分），請掃描下面微信號加群，備注：”昵稱+學校/公司+研究方向“，例如：”張三?+?上海交大?+?視覺SLAM“。請按照格式備注，否則不予通過。添加成功后會根據(jù)研究方向邀請進入相關微信群。請勿在群內(nèi)發(fā)送廣告，否則會請出群，謝謝理解~

算法工程師面試必考項：二叉樹