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

654.最大二叉树

代码随想录链接

题目

根据一个给定的数组, 使用数组中的最大值建立一个根节点, 再使用数组中最大值左侧的部分建立左子树, 使用数组中最大值右侧的部分建立右子树.

自己的想法

题目就很递归, 且给人的感觉像是前序遍历.

题解

递归法:

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.size() == 0) return NULL;
        if (nums.size() == 1) return new TreeNode(nums[0]); // 特殊情况处理
        int pivotIndex = 0, maxVal = INT_MIN;
        for (int i = 0; i < nums.size(); i++)               // 找最大值并根据最大值建立新节点.
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                pivotIndex = i;
            }
        TreeNode *root = new TreeNode(nums[pivotIndex]);

        vector<int> leftTreeNodes(nums.begin(), nums.begin() + pivotIndex);     // 左右分区
        vector<int> rightTreeNodes(nums.begin() + pivotIndex + 1, nums.end());

        root -> left = constructMaximumBinaryTree(leftTreeNodes);               // 递归地建立左右子树
        root -> right = constructMaximumBinaryTree(rightTreeNodes);

        return root;
    }
};

优化版的递归法: (主要优化在了没有建立新的数组, 每次递归时, 直接在原数组上进行分区)

class Solution {
private:
    TreeNode* constructMaximumBinaryTreeRecursive(vector<int>&nums, int left, int right) {
        if (left >= right) return NULL;         // 分区采用左闭右开区间, 左侧边界不能大于等于右侧边界

        int pivotIndex = left, maxVal = INT_MIN;    // 找分区中最大值并建立新节点
        for (int i = left; i < right; i++)
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                pivotIndex = i;
            }
        
        TreeNode *root = new TreeNode(nums[pivotIndex]);

        root -> left = constructMaximumBinaryTreeRecursive(nums, left, pivotIndex);     // 根据分区建立左右子树
        root -> right = constructMaximumBinaryTreeRecursive(nums, pivotIndex + 1, right);

        return root;

    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return constructMaximumBinaryTreeRecursive(nums, 0, nums.size());
    }
};

617.合并二叉树

代码随想录链接

题目

合并两棵二叉树, 如果位置相同的节点都存在的话, 则进行值的相加, 如果一棵树的子树不存在, 则将另外一棵树上相同位置的子树复制过来.

自己的想法

两棵树一起前/中/后序遍历, 都存在则值相加, 有一棵树不存在某侧子树则使用另一棵的进行覆盖.

题解

递归法:(作为懒狗只写了中序遍历, 前序和后序只需要调整值相加的语句的位置就能完成)

class Solution {
private:
    TreeNode* traversal(TreeNode *root1, TreeNode* root2) {
        if (!root1 && !root2) return nullptr;
        if (root1 && !root2) return root1;  // 处理一棵树上的一侧子树不存在而另一棵树上相应子树存在的情况
        if (!root1 && root2) return root2;

        root1 -> left = traversal(root1 -> left, root2 -> left);    // 递归合并左子树
        root1 -> val += root2 -> val;
        root1 -> right = traversal(root1 -> right, root2 -> right); // 递归合并右子树

        return root1;
    }
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        return traversal(root1, root2);
    }
};

迭代法:(把要比较的节点成对地入栈比较, 像101.对称二叉树那题一样)

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1) return root2;
        if (!root2) return root1;
        stack<TreeNode*> st;
        st.push(root2);
        st.push(root1);
        while (!st.empty()) {
            TreeNode *node1 = st.top(); st.pop();   // 连取两个节点进行对比
            TreeNode *node2 = st.top(); st.pop();

            node1 -> val += node2 -> val;           // 两个节点进行值相加

            if (node1 -> left && node2 -> left) {   // 都存在左子树, 左子树入栈合并
                st.push(node2 -> left);
                st.push(node1 -> left);
            }

            if (node1 -> right && node2 -> right) { // 都存在右子树, 右子树入栈合并
                st.push(node2 -> right);
                st.push(node1 -> right);
            }

            if (!(node1 -> left) && node2 -> left) {// 处理一侧不存在的情况
                node1 -> left = node2 -> left;
            }

            if (!(node1 -> right) && node2 -> right) {
                node1 -> right = node2 -> right;
            }
        }
        return root1;
    }
};

700.二叉搜索树中的搜索

代码随想录链接

题目

在二叉搜索树中找到带有给定值的节点.

自己的想法

就...搜呗, (根节点)大了往左边找, 小了往右边找.

题解

递归法:

class Solution {
private:
    TreeNode* traversal(TreeNode* root, int val) {
        if (!root) return nullptr;
        if (root -> val == val) return root; // 符合了就这个节点
        if (root -> val > val) return traversal(root -> left, val); // 大了往左边找
        if (root -> val < val) return traversal(root -> right, val);// 小了往右边找
        return nullptr;         // "我不到啊"
    }
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        return traversal(root, val);
    }
};

迭代法:

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) return nullptr;
        TreeNode *cur = root;       // 像不像遍历链表那样
        while (cur) {
            if (cur -> val == val) return cur;
            if (cur -> val > val) cur = cur -> left;    // 大了往左边找
            else cur = cur -> right;                    // 小了往右边找
        }
        return nullptr; // 没找到
    }
};

98.验证二叉搜索树

代码随想录链接

题目

判断给定的二叉树是否是二叉搜索树.

自己的想法

刚开始甚至还写了递归地判断左右孩子和遍历到的节点的大小关系, 这种情况就是忘了整个子树都要比根节点大/小的关系了. 自然是不行的.

看了题目的一些分析, 才回忆起来可以通过中序遍历的结果来进行判断, 又是王道上的题.都还回去了呜呜呜

题解

其实就中序遍历, 再加个遍历结果单调性的判断.

递归法:

class Solution {
private:
    vector<int> result;
    void traversal(TreeNode *root) {
        if (!root) return;
        traversal(root -> left);
        result.push_back(root -> val);  // 中序遍历
        traversal(root -> right);
    }
public:
    bool isValidBST(TreeNode* root) {
        traversal(root);
        for (int i = 1; i < result.size(); i++) {   // 遍历结果单调性判断
            if (result[i] <= result[i - 1]) return false;
        }
        return true;
    }
};

迭代法:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        vector<int> result;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {   // 中序遍历
            TreeNode *node = st.top();
            if (node) {
                st.pop();
                if (node -> right) st.push(node -> right);

                st.push(node);
                st.push(NULL);

                if (node -> left) st.push(node -> left);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node -> val);
            }
        }
        for (int i = 1; i < result.size(); i++) // 遍历结果单调性判断
            if (result[i] <= result[i - 1])
                return false;
        return true;
    }
};