代码随想录算法训练营第十七天|二叉树 part5

654.最大二叉树

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.size() == 0)
            return nullptr;
        auto max_iter = max_element(nums.begin(), nums.end());
        TreeNode* root = new TreeNode(*max_iter);

        if (nums.size() == 1)
            return root;
        
        vector<int> left(nums.begin(), max_iter);
        vector<int> right(max_iter + 1, nums.end());

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

        return root;
    }
};

617.合并二叉树

1. 参数和返回值：TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2)
2. 终止条件：如果有节点为null，则返回另一个节点
3. 单层逻辑：如果都不为null，val相加，然后递归处理左子树和右子树。

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

700.二叉搜索树中的搜索

递归

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

迭代

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

98.验证二叉搜索树

陷阱：二叉搜索树的根节点大于左子树包含的所有节点，小于右子树包含的所有节点。

使用中序遍历二叉搜索树是单调增的，根据这一点突破。

1. 参数和返回值：bool isValidBST(TreeNode* root)
2. 终止条件：遇到null返回true
3. 单层逻辑：递归遍历左子树，并且比较前后两个节点是否单调，然后递归遍历右子树，返回两个递归的和。

class Solution {
public:
    TreeNode* prev = nullptr;
    bool isValidBST(TreeNode* root) {
        if (root == nullptr)
            return true;
        
        bool left = isValidBST(root->left);
        if (prev != nullptr && prev->val >= root->val)
            return false;
        prev = root;
        bool right = isValidBST(root->right);
        return left && right;
    }
};

原文地址：https://blog.csdn.net/qq_43456971/article/details/140560794

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！