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

Leetcode654.最大二叉树

题目链接：654. 最大二叉树

Python：

class Solution:def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:if len(nums) == 1:node = TreeNode(nums[0])return nodemaxvalue, index = 0, 0for i in range(len(nums)):if nums[i] > maxvalue:maxvalue = nums[i]index = iroot = TreeNode(maxvalue)if index > 0:leftnums = nums[:index]root.left = self.constructMaximumBinaryTree(leftnums)if index < len(nums) - 1:rightnums = nums[index+1:]root.right = self.constructMaximumBinaryTree(rightnums)return root

Leetcode617.合并二叉树

题目链接：617. 合并二叉树

C++：

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 == nullptr) return root2;if(root2 == nullptr) return root1;root1->val += root2->val;root1->left = mergeTrees(root1->left, root2->left);root1->right = mergeTrees(root1->right, root2->right);return root1;}
};

Leetcode700.二叉搜索树中的搜索

题目链接：700. 二叉搜索树中的搜索

C++：（迭代法）

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while(root != nullptr){if(root->val > val)root = root->left;else if(root->val < val)root = root->right;elsereturn root;}return nullptr;}
};

Python：（递归）

class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if root == None or root.val == val:return rootresult = Noneif root.val > val:result = self.searchBST(root.left, val)if root.val < val:result = self.searchBST(root.right, val)return result

Leetcode98.验证二叉搜索树

题目链接：98. 验证二叉搜索树

C++：

class Solution {
public:TreeNode* pre = nullptr; // 用来记录前一个节点bool isValidBST(TreeNode* root) {if(root == nullptr) return true;bool sousuo_left = isValidBST(root->left);//中序遍历if(pre != nullptr && pre->val >= root->val)return false;pre = root;bool sousuo_right = isValidBST(root->right);return sousuo_left && sousuo_right;}
};