654.最大二叉树

    TreeNode* traverse(vector<int>& nums){if(nums.size() == 0){return nullptr;}if(nums.size() == 1){return new TreeNode(nums[0]);}int max_index = 0;int max = INT_MIN;for(int i = 0;i < nums.size(); i++){if(nums[i] > max){max = nums[i];max_index = i;}}TreeNode* root = new TreeNode(max);vector<int> leftnums(nums.begin(),nums.begin()+max_index);vector<int> rightnums(nums.begin()+max_index+1, nums.end());root->left = traverse(leftnums);root->right = traverse(rightnums);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.size() == 0){return nullptr;}return traverse(nums);}

617.合并二叉树

    TreeNode* traverse(TreeNode* root1, TreeNode* root2){if(root1 == nullptr && root2 == nullptr){return nullptr;}if(root1 == nullptr && root2 != nullptr){return root2;}if(root2 == nullptr && root1 != nullptr){return root1;}TreeNode* root = new TreeNode(root1->val + root2->val);root->left = traverse(root1->left, root2->left);root->right = traverse(root1->right, root2->right);return root;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 == nullptr && root2 == nullptr){return nullptr;}return traverse(root1, root2);}

700.二叉搜索树中的搜索

    TreeNode* searchBST(TreeNode* root, int val) {if(root == nullptr){return nullptr;} if(root->val == val){return root;}TreeNode* left_node = searchBST(root->left, val);TreeNode* right_node = searchBST(root->right, val);if(left_node) return left_node;if(right_node) return right_node;return nullptr;}

98.验证有效二叉搜索树

//容易进入误区

bool traverse(TreeNode* node){if(node == nullptr){return true;}//错误理解，二叉搜索树是整个左子树比当前节点小，右子树比当前节点大，而非局部子树内满足就可以if(node->left && node->left->val >= node->val){return false;}if(node->right && node->right->val <= node->val){return false;}bool left_flag = traverse(node->left);bool right_flag = traverse(node->right);if(!left_flag || !right_flag){return false;}return true;}bool isValidBST(TreeNode* root) {return traverse(root); }

//正确写法

    TreeNode* pre;bool isValidBST(TreeNode* root) {if(root == nullptr){return true;}bool left_flag = isValidBST(root->left);if(pre && pre->val >= root->val){return false;}pre = root;bool right_flag = isValidBST(root->right);return left_flag && right_flag;}