代码随想录算法训练营Day-17 | 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

654.最大二叉树和中序后序数组构造二叉树的思路一致要更简单一些。思路1.如果数组为空返回NULL2.然后开始找数组最大值根据这个最大值创建根节点3.以最大值为中心分割出左数组和右数组4.根节点的左孩子为左数组构建出的子树5.根节点的右孩子为右数组构建出的子树优化省去在每个调用都创建新数组的过程可以使用左右索引来替代函数传入根节点和左右索引左右索引可再原数组上进行切割效果相同。class Solution { public: TreeNode* traversal(vectorint nums, int left, int right){ if(rightleft) return NULL; int idxleft; for(int ileft1; iright; i){ if(nums[i]nums[idx]) idx i; } TreeNode* root new TreeNode(nums[idx]); root-left traversal(nums, left, idx); root-right traversal(nums, idx1, right); return root; } TreeNode* constructMaximumBinaryTree(vectorint nums) { return traversal(nums,0,nums.size()); } };617.合并二叉树思路终止条件是遇到1节点为空就返回2节点遇到2节点为空就返回1节点包含了所有三种情况进行前序遍历先执行两节点值相加的操作然后执行左右遍历的操作并用t1节点的左右孩子节点接住注意遍历时要同步遍历TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if(!t1) return t2; if(!t2) return t1; t1-val t2-val; t1-left mergeTrees(t1-left, t2-left); t1-right mergeTrees(t1-right, t2-right); return t1; }700.二叉搜索树中的搜索递归法思路遇到空节点返回空遇到值节点返回值节点遇到的节点值大于值返回调用左子树到的节点值小于值返回调用右子树利用二叉搜索树的左小右大的特性。TreeNode* searchBST(TreeNode* root, int val) { if(root NULL) return NULL; if(root-val val) return root; if(root-val val) return searchBST(root-left,val); if(root-val val) return searchBST(root-right,val); return NULL; }迭代法思路搜索二叉树路径是固定的迭代法很简单。如果节点不为空就一直遍历下去遇到值节点返回值节点遇到的节点值大于值就更新节点为它的左孩子继续搜索遇到的节点值小于值就更新节点为它的右孩子继续搜索。TreeNode* searchBST(TreeNode* root, int val) { while(root!NULL){ if(root-val val) return root; else if(root-val val) root root-left; else root root-right; } return NULL; }98.验证二叉搜索树本题有两个思路一个是使用中序遍历得到数组数组如果严格递增就说明是二叉搜索树class Solution { public: vectorint result; void traversal(TreeNode* root){ if(root NULL) return; traversal(root-left); result.push_back(root-val); traversal(root-right); return; } bool isValidBST(TreeNode* root) { traversal(root); for(int i1;iresult.size();i){ if(result[i] result[i-1]) return false; } return true; } };另一个也是中序遍历然后在遍历中判断当前节点是不是大于最大值最大值一直在更新如果不是大于就返回false最后返回左子树和右子树的调用结果的。long long maxValue LONG_MIN; bool isValidBST(TreeNode* root) { if(rootNULL) return true; bool left isValidBST(root-left); if(maxValueroot-val) maxValue root-val; else return false; bool right isValidBST(root-right); return left right; }