代码随想录day20

标签：node TreeNode val nums root1 代码 随想录 day20 root

654. 最大二叉树

解题步骤：

1、确定递归函数的参数和返回值

TreeNode* constructMaximumBinaryTree(vector<int>& nums) 2、确定终止条件

1 TreeNode* node = new TreeNode(0);
2 if (nums.size() == 1) {
3     node->val = nums[0];
4     return node;
5 }

当传入数组大小为1时，说明已经遍历到叶子结点，遍历结束，返回叶子节点。

3、确定单层递归的逻辑

　　①找到最大值，记录值和索引，并以此为根节点；

 1 int maxValue = 0;
 2 int maxValueIndex = 0;
 3 for (int i = 0; i < nums.size(); i++) {
 4     if (nums[i] > maxValue) {
 5         maxValue = nums[i];
 6         maxValueIndex = i;
 7     }
 8 }
 9 TreeNode* node = new TreeNode(0);
10 node->val = maxValue;

　　②构造左子树；

1 if (maxValueIndex > 0) {
2     vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
3     node->left = constructMaximumBinaryTree(newVec);
4 }

　　③构造右子树。

1 if (maxValueIndex < (nums.size() - 1)) {
2     vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
3     node->right = constructMaximumBinaryTree(newVec);
4 }

617. 合并二叉树

递归法解题步骤：

1、确定递归函数参数和返回值

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) 2、确定递归结束的条件         if (root1 == nullptr) return root2;         if (root2 == nullptr) return root1; 3、确定递归单层的逻辑        root->val = root1->val + root2->val; 代码如下：

 1 class Solution {
 2 public:
 3     TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
 4         if (root1 == nullptr) return root2;
 5         if (root2 == nullptr) return root1;
 6         //重新定义根节点
 7         TreeNode* root = new TreeNode(0);
 8         root->val = root1->val + root2->val;
 9         root->left = mergeTrees(root1->left, root2->left);
10         root->right = mergeTrees(root1->right, root2->right);
11         return root;
12     }
13 };

700. 二叉搜索树中的搜索

代码如下：

 1 class Solution {
 2 public:
 3     TreeNode* searchBST(TreeNode* root, int val) {
 4         queue<TreeNode*> que;
 5         if (root != nullptr) que.push(root);
 6         while(!que.empty()){
 7             int size = que.size();
 8             while (size--){
 9                 TreeNode* node = que.front();
10                 que.pop();
11                 if (node->val == val){
12                     return node;
13                 }
14                 if (node->left) que.push(node->left);
15                 if (node->right) que.push(node->right);
16             }
17         }
18         return nullptr;
19     }
20 };

98. 验证二叉搜索树

 1 class Solution {
 2 private:
 3     vector<int> vec;
 4     void traversal(TreeNode* root) {
 5         if (root == NULL) return;
 6         traversal(root->left);
 7         vec.push_back(root->val); // 将二叉搜索树转换为有序数组
 8         traversal(root->right);
 9     }
10 public:
11     bool isValidBST(TreeNode* root) {
12         vec.clear(); // 不加这句在leetcode上也可以过，但最好加上
13         traversal(root);
14         for (int i = 1; i < vec.size(); i++) {
15             // 注意要小于等于，搜索树里不能有相同元素
16             if (vec[i] <= vec[i - 1]) return false;
17         }
18         return true;
19     }
20 };

 

   

标签：node,TreeNode,val,nums,root1,代码,随想录,day20,root
From： https://www.cnblogs.com/zsqy/p/16800588.html