KW45/20：了解了二叉樹的概念和遞回的思想，一共練習3個題目，現在總結如下，
第一題：最大二叉樹，給定一個陣列，二叉樹的根是陣列中的最大元素，左子樹是通過陣列中最大值左邊部分構造的最大二叉樹，右子樹是通過陣列中最大值右邊部分構造的最大二叉樹
- 思路：二叉樹的根是陣列中的最大元素，左子樹是最大值左邊部分陣列的最大二叉樹，右子樹是最大值右邊部分陣列的最大二叉樹，遞回出口是陣列為空，回傳None，
- 代碼：
class Solution:
"""
@param nums: an array
@return: the maximum tree
"""
def constructMaximumBinaryTree(self, nums):
# Write your code here
if not nums: # 遞回的出口
return None
max_val = max(nums) # 串列中的最大值
max_idx = nums.index(max_val) # 得到最大值的索引
root = TreeNode(nums[max_idx]) # 最大值是二叉樹的根節點
# 根據最大值左邊部分陣列構造最大二叉樹
root.left = self.constructMaximumBinaryTree(nums[:max_idx])
# 根據最大值右邊部分陣列構造最大二叉樹
root.right = self.constuctMaximumBinaryTree(nums[max_idx + 1:])
return root
第二題：二叉樹的最大深度，給定一個二叉樹，找出其最大深度
- 思路：找出左子樹的最大深度和右子樹的最大深度，這兩個的最大值再加1就是這個二叉樹的最大深度，遞回出口是二叉樹為空，回傳0，
- 代碼：
class Solution:
"""
@param root: The root of binary tree.
@return: An integer
"""
def maxDepth(self, root):
# write your code here
if root == None:
return 0
else:
return 1+ max(self.maxDepth(root.left), self.maxDepth(root.right))
第三題：驗證二叉查找樹，判斷一個二叉樹是不是有效的二叉查找樹，即節點的左子樹都小于當前節點，節點的右子樹都大于當前節點，左右子樹也是二叉查找樹
- 思路：因為在練習遞回，很自然地想到判斷左子樹和右子樹是否都是二叉查找樹，不是的話，回傳False，但是這里有一個容易忽略的點，即左子樹必須小于上一層節點，右子樹必須大于上一層節點，遞回出口是節點為空，回傳True或者節點不滿足二叉查找樹的定義，回傳False，
- 代碼：
class Solution:
"""
@param root: The root of binary tree.
@return: True if the binary tree is BST, or false
"""
def isValidBST(self, root):
# write your code here
# 定義一個幫助函式來判斷是否滿足二叉查找樹的定義
def helper(root, lower=float('-inf'), upper=float('inf')):
if root == None: # 節點為空滿足二叉查找樹的定義
return True
val = root.val
if val <= lower or val >= upper: # 節點不在上下界內，不滿足···定義
return False
# 判斷左右子樹是否滿足···定義
if not helper(root.left, lower, val):
return False
if not helper(root.right, val, upper):
return False
return True # 如果沒有找到不滿足···定義的節點，回傳True
return helper(root)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/208745.html
標籤：其他