[代码随想录17]二叉树之最大二叉树、合并二叉树、二搜索树中的搜索、验证二叉搜索树。

前言

二叉树的题目还是要会一流程构造函数之类的。其中还有回溯的思想

题目链接

654. 最大二叉树 - 力扣（LeetCode）

一、最大二叉树

 思路：还是考察构造二叉树，简单来说就是给你一个数组去构建一个二叉树，递归来解决就可以，复杂来说，给你一个数组，构建一颗每个节点都最大的数。所以我们先循环找到一个最大的根节点，然后再左边和右边构建即可。根节点去划分区间

 

TreeNode* traversal(vector<int>& nums,int left,int right){if(left>=right) return nullptr;int maxValueIndex=left;for(int i=left+1;i<right;i++){if(nums[i]>nums[maxValueIndex]) maxValueIndex=i;}TreeNode* root=new TreeNode(nums[maxValueIndex]);root->left=traversal(nums,left,maxValueIndex);root->right=traversal(nums,maxValueIndex+1,right);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return traversal(nums,0,nums.size());}

 

二、合并二叉树

 

三、二叉搜索树中的搜索

 

四、验证二叉搜索树