題目簡介
654:最大二叉樹
給定一個不重復的整數(shù)數(shù)組 nums 。 最大二叉樹 可以用下面的算法從 nums 遞歸地構建:
創(chuàng)建一個根節(jié)點匆瓜，其值為 nums 中的最大值赢笨。
遞歸地在最大值 左邊 的 子數(shù)組前綴上 構建左子樹。
遞歸地在最大值 右邊 的 子數(shù)組后綴上 構建右子樹驮吱。
返回 nums 構建的 最大二叉樹 茧妒。
617:合并二叉樹
想象一下，當你將其中一棵覆蓋到另一棵之上時左冬，兩棵樹上的一些節(jié)點將會重疊（而另一些不會）桐筏。你需要將這兩棵樹合并成一棵新二叉樹。合并的規(guī)則是：如果兩個節(jié)點重疊拇砰，那么將這兩個節(jié)點的值相加作為合并后節(jié)點的新值梅忌；否則，不為 null 的節(jié)點將直接作為新二叉樹的節(jié)點除破。
返回合并后的二叉樹铸鹰。
注意: 合并過程必須從兩個樹的根節(jié)點開始。
700:二叉搜索樹中的搜索
給定二叉搜索樹（BST）的根節(jié)點 root 和一個整數(shù)值 val皂岔。
你需要在 BST 中找到節(jié)點值等于 val 的節(jié)點蹋笼。 返回以該節(jié)點為根的子樹。 如果節(jié)點不存在躁垛，則返回 null
98:驗證二叉搜索樹
給你一個二叉樹的根節(jié)點 root 剖毯，判斷其是否是一個有效的二叉搜索樹。
有效 二叉搜索樹定義如下：
節(jié)點的左子樹只包含 小于 當前節(jié)點的數(shù)教馆。
節(jié)點的右子樹只包含 大于 當前節(jié)點的數(shù)逊谋。
所有左子樹和右子樹自身必須也是二叉搜索樹。
初見思路
復盤思路
- 參考從前序和中序遍歷二叉樹土铺，每次找到最大點位置然后構建二叉樹即可
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return None
root_val = sorted(nums)[-1]
root = TreeNode(root_val)
max_idx = nums.index(root_val)
root.left = self.constructMaximumBinaryTree(nums[:max_idx])
root.right = self.constructMaximumBinaryTree(nums[max_idx+1:])
return root
- 按照題目意思來即可
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
node = None
if not root1:
return root2
elif not root2:
return root1
else:
node = TreeNode(root1.val+root2.val)
node.left = self.mergeTrees(root1.left, root2.left)
node.right = self.mergeTrees(root1.right, root2.right)
return node
- 層序遍歷胶滋，YYDS.
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return None
queue = collections.deque([root])
while queue:
size = len(queue)
for _ in range(size):
node = queue.popleft()
if node.val == val:
return node
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return None
- 直接按題目意思來，可以直接解決
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
return self.isValid(root,float('-inf'),float('inf'))
def isValid(self,root,left_val,right_val) -> bool:
if not root:
return True
if root.val <= left_val or root.val >= right_val:
return False
return self.isValid(root.left , left_val, root.val) and self.isValid(root.right, root.val, right_val)
重點難點
https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html
https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html
https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
