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 };

 

原文地址：http://www.cnblogs.com/zsqy/p/16800588.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性