前言
今日文案：
猫喜欢吃鱼，猫却不能下水，鱼喜欢吃蚯蚓，鱼却不能上岸，人生，就是一边拥有，一边失去，一边选择，一边放弃。
一、最大二叉树
解题思路：
主要也是分割数组思想。
class Solution { public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { TreeNode*root=new TreeNode(0); if(nums.size()==1) { root->val=nums[0]; //数组只有一个数的时候，可以直接返回 return root; } int max=-100,maxindex=0; for(int i=0;i<nums.size();i++) //遍历数组 { if(nums[i]>max) //找出最大值及其下标 { max=nums[i]; maxindex=i; } } root->val=max; //建好中节点数值 if(maxindex>0) //判断左子树是否有元素 { vector<int> lefttree(nums.begin(),nums.begin()+maxindex); root->left=constructMaximumBinaryTree(lefttree); } if(maxindex<nums.size()-1) //判断右子树是否有元素 { vector<int> righttree(nums.begin()+maxindex+1,nums.end()); root->right=constructMaximumBinaryTree(righttree); } return root; } };
二、合并二叉树
解题思路：
同时遍历两棵树，同一位置都有就加起来，有空就用另外一棵树补。构造一般用前序。
class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if(root1==NULL) //一个有空就返回另外一个 { return root2; } if(root2==NULL) { return root1; } TreeNode*node=new TreeNode(0); //建立节点 node->val=root1->val+root2->val; //都有就加起来 node->left=mergeTrees(root1->left,root2->left); //遍历 node->right=mergeTrees(root1->right,root2->right); return node; } };
三、二叉搜索树中的搜索
class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { if(root==NULL) { return NULL; } if(root->val==val) //找到了就返回 { return root; } if(root->left==NULL&&root->right==NULL) //叶子节点也返回 { return NULL; } TreeNode*node=NULL; //创建节点存值 if(val>root->val) //根据搜索树的定义，分两边搜索 { node=searchBST(root->right,val); } if(val<root->val) { node=searchBST(root->left,val); } return node; } };
四、验证二叉树搜索
class Solution { public: long long maxval=LONG_MIN; //设定最小值 bool isValidBST(TreeNode* root) { if(root==0) { return true; //空节点就返回 } bool left=isValidBST(root->left); //左遍历 if(maxval<root->val) //一层一层赋值，递增 { maxval=root->val; } else //有违法的直接false，就再也没有机会翻身了。 { return false; } bool right=isValidBST(root->right); return right&&left; } };
总结
感觉囫囵吞枣，好烦，感觉还是没有分清楚，前中后序遍历的过程，贪多嚼不烂了。
