654.最大二叉樹
1.題目
給定一個不重複的整數數組 nums 。 最大二叉樹 可以用下面的算法從 nums 遞歸地建構:
建立一個根節點,其值為 nums 中的最大值。
遞歸地在最大值 左邊 的 子數組字首上 建構左子樹。
遞歸地在最大值 右邊 的 子數組字尾上 建構右子樹。
傳回 nums 建構的 最大二叉樹 。
654.最大二叉樹
2.實作
實作原理和用前序+中序周遊數組建構二叉樹類似,而且要簡單些~
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
# 構造二叉樹,尋找最大值
if len(nums) == 0:
return None
tmp, index = -1, -1
for i in range(len(nums)):
if tmp < nums[i]:
tmp = nums[i]
index = i
root = TreeNode(tmp)
root.left = self.constructMaximumBinaryTree(nums[:index])
root.right = self.constructMaximumBinaryTree(nums[index+1:])
return root
3.文章講解
優化部分——終止條件可以改為:
if len(nums) == 1:
node = Treenode(nums[0])
return node
題目拓展:合并二叉樹
700. 二叉搜尋樹中的搜尋
1.題目
給定二叉搜尋樹(BST)的根節點 root 和一個整數值 val。你需要在 BST 中找到節點值等于 val 的節點。 傳回以該節點為根的子樹。 如果節點不存在,則傳回 null 。
700. 二叉搜尋樹中的搜尋
2.實作
雖然簡單,但二叉樹的特點得好好總結下
1.對于樹中的每個節點X,它的左子樹中所有值小于根的值,而它的右子樹中所有值大于根的值。根據這個性質,對一個二叉樹進行中序周遊,如果是單調遞增的,則可以說明這個樹是二叉搜尋樹。
2.二叉搜尋樹不要求是完全二叉樹,上述值得比較僅針對有節點值的節點而言
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
# 二叉搜尋樹的有序性避免了回溯,是以此時無需棧和隊列來輔助周遊節點,隻需自頂向下确定搜尋方向
if not root:
return None
if root.val == val:
return root
elif root.val < val:
return self.searchBST(root.right, val)
else:
return self.searchBST(root.left, val)
3.文章講解
嘗試下疊代法解決,此時利用二叉樹的特點隻需自頂向下二分查找,不需要回溯
98. 驗證二叉搜尋樹
1.題目
給你一個二叉樹的根節點 root ,判斷其是否是一個有效的二叉搜尋樹。
有效 二叉搜尋樹定義如下:
節點的左子樹隻包含 小于 目前節點的數。
節點的右子樹隻包含 大于 目前節點的數。
所有左子樹和右子樹自身必須也是二叉搜尋樹
98. 驗證二叉搜尋樹
2.複習前
1)沒有注意到左右子樹的所有節點與根的關系,而隻是簡單比較左右根的大小
2)以為二叉搜尋樹除葉子節點外沒有空節點
3.實作
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
# 有個問題是要保證子樹的所有節點都需滿足與根的關系
# 用中序周遊,疊代的方法加入節點,如果嚴格單調遞增,則有效
# 不需要用數組來記錄,隻需要一點前節點即可pre=None(初始化) if pre and。。。。。。
nodes = []
stack = []
if not root:
return True
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
if nodes and cur.val <= nodes[-1]:
return False
nodes.append(cur.val)
cur = cur.right
return True
4.文章講解
對于自己寫的用數組來記錄節點值,是可用前後節點來優化的哦!