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

654.最大二叉树

和中序后序数组构造二叉树的思路一致，要更简单一些。

思路：

1.如果数组为空，返回NULL

2.然后开始找数组最大值，根据这个最大值创建根节点

3.以最大值为中心，分割出左数组和右数组

4.根节点的左孩子为左数组构建出的子树

5.根节点的右孩子为右数组构建出的子树

优化：

省去在每个调用都创建新数组的过程，可以使用左右索引来替代，函数传入根节点和左右索引，左右索引可再原数组上进行切割，效果相同。

class Solution { public: TreeNode* traversal(vector<int>& nums, int left, int right){ if(right<=left) return NULL; int idx=left; for(int i=left+1; i<right; ++i){ if(nums[i]>nums[idx]) idx = i; } TreeNode* root = new TreeNode(nums[idx]); root->left = traversal(nums, left, idx); root->right = traversal(nums, idx+1, right); return root; } TreeNode* constructMaximumBinaryTree(vector<int>& 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: vector<int> 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 i=1;i<result.size();i++){ if(result[i] <=result[i-1]) return false; } return true; } };

另一个也是中序遍历，然后在遍历中判断当前节点是不是大于最大值（最大值一直在更新），如果不是大于，就返回false，最后返回左子树和右子树的调用结果的&&。

long long maxValue = LONG_MIN; bool isValidBST(TreeNode* root) { if(root==NULL) return true; bool left = isValidBST(root->left); if(maxValue<root->val) maxValue = root->val; else return false; bool right = isValidBST(root->right); return left && right; }