代码随想录算法训练营第二十天|654. 最大二叉树、617. 合并二叉树、700. 二叉搜索树中的搜索、98. 验证二叉搜索树

【参考链接】

654. 最大二叉树

【注意】

1.构造二叉树，都需要用前序遍历。

2.二叉树的根是数组中的最大元素。

3.没必要构造新数组，通过下标控制左右区间。运行效率会高很多。

【代码】

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution(object):
 8     def constructMaximumBinaryTree(self, nums):
 9         """
10         :type nums: List[int]
11         :rtype: TreeNode
12         """
13         if not nums:
14             return None
15         #中
16         maxvalue = max(nums)
17         index = nums.index(maxvalue)
18 
19         root = TreeNode(maxvalue)
20         left = nums[:index]#左闭右开
21         right = nums[index+1:]
22 
23         #左
24         root.left = self.constructMaximumBinaryTree(left)
25         #右
26         root.right = self.constructMaximumBinaryTree(right)
27         return root

617. 合并二叉树

【注意】

1.合并必须从两个树的根节点开始。

2.前序遍历 。其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。

【代码】

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution(object):
 8     def mergeTrees(self, root1, root2):
 9         """
10         :type root1: TreeNode
11         :type root2: TreeNode
12         :rtype: TreeNode
13         """
14         # 递归终止条件: 
15         #  但凡有一个节点为空, 就立刻返回另外一个. 如果另外一个也为None就直接返回None. 
16         if not root1:
17             return root2
18         if not root2:
19             return root1
20         
21         # 上面的递归终止条件保证了代码执行到这里root1, root2都非空. 
22         root1.val += root2.val
23         root1.left = self.mergeTrees(root1.left,root2.left)
24         root1.right = self.mergeTrees(root1.right,root2.right)
25 
26         return root1

700. 二叉搜索树中的搜索

【注意】

1.二叉搜索树是一个有序树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树

【代码】

# 为什么要有返回值: 
#   因为搜索到目标节点就要立即return，
#   这样才是找到节点就返回（搜索某一条边），如果不加return，就是遍历整棵树了。

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution(object):
 8     def searchBST(self, root, val):
 9         """
10         :type root: TreeNode
11         :type val: int
12         :rtype: TreeNode
13         """
14         #递归法
15         if not root or root.val == val:
16             return root
17         
18         if root.val > val:
19             return self.searchBST(root.left, val)
20         
21         if root.val < val:
22             return self.searchBST(root.right, val)
23         
24         #迭代法-利用二叉搜索树的特性
25         while root is not None:
26             if val < root.val: root = root.left
27             elif val > root.val: root = root.right
28             else: return root
29         return None

98. 验证二叉搜索树

【注意】

1.按左中右顺序遍历，就是有序数组---是否是单调递增的。--中序遍历。

【代码】