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

刷题笔记day20

654.最大二叉树

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

借鉴使用中序和后序遍历序列构造二叉树，对最大二叉树进行区间划分。

自己写的代码

class Solution {
public:
    TreeNode* getmaxtree(vector<int>& nums, int begin, int end) {
        if (begin >= end) return NULL;
        int maxnumindex = begin;
        // 找出最大值
        for (int i = begin + 1; i < end; ++i) {
            if (nums[i] > nums[maxnumindex]) {
                maxnumindex = i;
            }
        }
        TreeNode* node = new TreeNode(nums[maxnumindex]);
        // 左闭右开
        int leftbegin = begin;
        int leftend = maxnumindex;
        int rightbegin = maxnumindex + 1;
        int rightend = end;
        node->left = getmaxtree(nums, leftbegin, leftend);
        node->right = getmaxtree(nums, rightbegin, rightend);
        return node;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return getmaxtree(nums, 0, nums.size());
    }
};

看了题解后的收获

直接使用索引作为函数输入相比于使用vector数组作为输入效率高了很多。

617.合并二叉树

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

采用前序遍历的方式，对两颗二叉树进行遍历，选一棵树作为和树，return。

自己写的代码

class Solution {
public:
    TreeNode* merge(TreeNode* node1, TreeNode* node2) {
        if (!node1) return node2;
        if (!node2) return node1;
        node1->val += node2->val;
        node1->left = merge(node1->left, node2->left);
        node1->right = merge(node1->right, node2->right);
        return node1;
    }
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        return merge(root1, root2);
    }
};

看了题解后的收获

和遍历逻辑一样，只不过传入两个树的节点，同时操作。

700.二叉搜索树中的搜索

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

迭代法相当简单。

自己写的代码

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root) {
            if (root->val > val) root = root->left;
            else if (root->val < val) root = root->right;
            else return root;
        }
        return root;
    }
};

看了题解后的收获

递归法也可以实现，要注意每一层return result。

98.验证二叉搜索树

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

用前序遍历做。复习一遍前序遍历模板。

自己写的代码

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        if (!root) return true;
        st.push(root);
        TreeNode* pre = NULL; // 记录前一个节点
        while (!st.empty()) {
            TreeNode* cur = st.top();
            if (cur != NULL) {
                st.pop();
                if (cur->right) st.push(cur->right); // 右
                st.push(cur);   // 中
                st.push(NULL);  
                if (cur->left) st.push(cur->left); // 左
            } else {
                st.pop();
                cur = st.top();                
                st.pop();
                if (pre != NULL && cur->val <= pre->val) return false;
                pre = cur; //保存前一个访问的结点
            }
        }
        return true;
    }
};

看了题解后的收获

可以用中序遍历判断是否有序，也可以用递归法。记录前一个结点。