654. 最大二叉树
题目链接：https://leetcode.cn/problems/maximum-binary-tree/
算法思想：
采用前序遍历，找到最大值作为根节点，然后递归左右子树元素。
凡是构造二叉树的题目都要用前序遍历。
class Solution {
public:
TreeNode* preorder(vector<int>& nums, int start, int end)
{
if(start>=end)
return NULL;
//寻找最大值
int pos = start;
int max=nums[start];
for(int i=start;i<end;i++)
{
if(nums[i] > max)
{
max = nums[i];
pos = i;
}
}
TreeNode* node = new TreeNode(max);
if(end-start==1)
return node;
node->left = preorder(nums, start,pos);
node->right = preorder(nums, pos+1, end);
return node;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return preorder(nums,0,nums.size());
}
};
617. 合并二叉树
题目链接：https://leetcode.cn/problems/merge-two-binary-trees/
算法思想：合并两棵二叉树，使用前序遍历。构建二叉树的题目都要使用前序遍历。
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1==NULL&&root2==NULL)
return NULL;
if(root1!=NULL&&root2==NULL)
return root1;
if(root1==NULL&&root2!=NULL)
return root2;
int val = root1->val + root2->val;
TreeNode* node = new TreeNode(val);
node->left = mergeTrees(root1->left, root2->left);
node->right = mergeTrees(root1->right, root2->right);
return node;
}
};
700. 二叉搜索树中的搜索
题目链接：https://leetcode.cn/problems/search-in-a-binary-search-tree/
代码：
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if(root==NULL)
return NULL;
if(root->val == val)
return root;
if(root->val<val)
return searchBST(root->right,val);
else
return searchBST(root->left,val);
}
};
98. 验证二叉搜索树
题目链接：https://leetcode.cn/problems/validate-binary-search-tree/
采用后续遍历的方法
class Solution {
public:
TreeNode* pre=NULL;
bool inorder(TreeNode*root)
{
if(root==NULL)
return true;
bool left= inorder(root->left);
if(pre!=NULL&&pre->val>=root->val)
return false;
pre = root;
bool right= inorder(root->right);
return left&&right;
}
bool isValidBST(TreeNode* root) {
return inorder(root);
}
};
