【算法训练营day20】LeetCode654. 最大二叉树 LeetCode617. 合并二叉树 LeetCode700. 二叉搜索树中的搜索 LeetCode98. 验证二叉搜索树

LeetCode654. 最大二叉树

题目链接：654. 最大二叉树

初次尝试

和昨天最后一题的思路很像，本质上都是递归构建二叉树。

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.size() == 0) return NULL;

        int max_index, temp = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > temp) {
                temp = nums[i];
                max_index = i;
            }
        }
        
        TreeNode* root = new TreeNode(nums[max_index]);
        vector<int> left_nums(nums.begin(), nums.begin() + max_index);
        vector<int> right_nums(nums.begin() + max_index + 1, nums.end());

        root -> left = constructMaximumBinaryTree(left_nums);
        root -> right = constructMaximumBinaryTree(right_nums);

        return root; 
    }
};

看完代码随想录后的想法

思路差不多。

LeetCode617. 合并二叉树

题目链接：617. 合并二叉树

初次尝试

写的比较复杂，思路就是前序递归遍历两个树，对应节点进行合并。

class Solution {
public:
    TreeNode* traversal(TreeNode* node1, TreeNode* node2) {
        if (node1 == NULL && node2 == NULL) return NULL;
        TreeNode* root = new TreeNode();
        if (node1 == NULL) {
            root -> val = node2 -> val;
            root -> left = traversal(NULL, node2 -> left);
            root -> right = traversal(NULL, node2 -> right);
        }
        else if (node2 == NULL) {
            root -> val = node1 -> val;
            root -> left = traversal(node1 -> left, NULL);
            root -> right = traversal(node1 -> right, NULL);
        }
        else {
            root -> val = node1 -> val + node2 -> val;
            root -> left = traversal(node1 -> left, node2 -> left);
            root -> right = traversal(node1 -> right, node2 -> right);
        }
        return root;
    }

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

看完代码随想录后的想法

果然想复杂了，其实可以直接利用两个现成的树，没有必要声明新的节点。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1) return root2;
        if (!root2) return root1;

        root1 -> val += root2 -> val;
        root1 -> left = mergeTrees(root1 -> left, root2 -> left);
        root1 -> right = mergeTrees(root1 -> right, root2 -> right);

        return root1;
    }
};

LeetCode700. 二叉搜索树中的搜索

题目链接：700. 二叉搜索树中的搜索

初次尝试

比较常规的一道二叉树遍历题，一遍ac。

class Solution {
public:
    TreeNode* traversal(TreeNode* node, int val) {
        if (node == NULL) return NULL;
        if (node -> val == val) return node;

        TreeNode* left_node = traversal(node -> left, val);
        TreeNode* right_node = traversal(node -> right, val);
        if (left_node) return left_node;
        if (right_node) return right_node;
        return NULL; 
    }
    TreeNode* searchBST(TreeNode* root, int val) {
        return traversal(root, val);   
    }
};

看完代码随想录后的想法

上面思路没有利用二叉搜索树的有序性，改进后的代码如下。

class Solution {
public:
    TreeNode* traversal(TreeNode* node, int val) {
        if (node == NULL || node -> val == val) return node;

        if (node -> val > val) return traversal(node -> left, val);
        if (node -> val < val) return traversal(node -> right, val);
        return NULL;
    }

    TreeNode* searchBST(TreeNode* root, int val) {
        return traversal(root, val);   
    }
};

LeetCode98. 验证二叉搜索树

题目链接：98. 验证二叉搜索树

初次尝试

陷入了陷阱：

• 陷阱1

不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。

这是因为二叉搜索树的定义为：

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

注意是节点整个左子树的所有值都要小于当前节点值，而不仅仅是左子节点一个节点。

看完代码随想录后的想法

要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

所以可以中序递归遍历，判断节点值是否递增，要注意样例中最小节点可能是int的最小值，如果这样使用最小的int来比较也是不行的。

此时可以初始化比较元素为longlong的最小值。

class Solution {
public:
    long long max_val = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if (!root) return true;

        bool left = isValidBST(root -> left);
        if (root -> val > max_val) max_val = root -> val;
        else return false;
        bool right = isValidBST(root -> right);

        return left && right;
    }
};