Day 20 二叉樹

654. 最大二叉樹

遞歸

class Solution {
    TreeNode *build(const vector<int> &nums, int left, int right)
    {
        if (left >= right) return nullptr;
        int idx = left;
        for (int i = left + 1; i < right; ++i) 
        {
            if (nums[i] > nums[idx])
            {
                idx = i;
            }
        }
        TreeNode *root = new TreeNode(nums[idx]);
        root->left = build(nums, left, idx);
        root->right = build(nums, idx + 1, right);
        return root;
    }

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

617. 合并二叉樹

遞歸

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

迭代

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

        queue<TreeNode*> que;

        que.push(root1);
        que.push(root2);

        TreeNode *cur1, *cur2;
        while (!que.empty())
        {
            cur1 = que.front();
            que.pop();
            cur2 = que.front();
            que.pop();

            cur1->val = cur1->val + cur2->val;

            if (cur1->left && cur2->left)
            {
                que.push(cur1->left);
                que.push(cur2->left);
            }

            if (cur1->right && cur2->right)
            {
                que.push(cur1->right);
                que.push(cur2->right);
            }

            if (!cur1->left && cur2->left)
            {
                cur1->left = cur2->left;
            }

            if (!cur1->right && cur2->right)
            {
                cur1->right = cur2->right;
            }
        }

        return root1;
    }
};

700. 二叉搜索樹中的搜索

遞歸

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

迭代

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        TreeNode *cur = root;

        while (cur)
        {
            if (cur->val > val)
            {
                cur = cur->left;
            }
            else if (cur->val < val)
            {
                cur = cur->right;
            }
            else
            {
                return cur;
            }
        }

        return nullptr;
    }
};

98. 驗(yàn)證二叉搜索樹

遇到兩個(gè)坑的地方：

1. 遞歸的時(shí)候，不能光驗(yàn)證左子樹的根節(jié)點(diǎn)小于當(dāng)前根節(jié)點(diǎn)，右子樹的根節(jié)點(diǎn)大于但當(dāng)前根節(jié)點(diǎn)，別忘了左子樹上的每一個(gè)節(jié)點(diǎn)都要求比根節(jié)點(diǎn)要小，右子樹上的每一個(gè)節(jié)點(diǎn)都要求比根節(jié)點(diǎn)大。
2. 根節(jié)點(diǎn)跟左（右）子樹中的某一個(gè)節(jié)點(diǎn)相等，也是不符合二叉搜索樹的規(guī)則的

遞歸

用記錄前一個(gè)節(jié)點(diǎn)的方法來處理文章來源地址http://www.zghlxwxcb.cn/news/detail-600850.html

class Solution {    
    TreeNode *pre = nullptr;
    bool flag = true;

    void tracking(TreeNode *root)
    {
        if (!root) return;
        tracking(root->left);
        if (pre)
        {
            if (root->val <= pre->val) // 注意：這里是等號(hào)，兩值相等也不符合
            {
                flag = false;
            }
        }
        pre = root;
        tracking(root->right);
    }

public:
    bool isValidBST(TreeNode* root) {
        tracking(root);
        return flag;
    }
};

迭代

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> table;

        TreeNode *cur = root;
        while (cur || !stk.empty())
        {
            if (cur)
            {
                stk.push(cur);
                cur = cur->left;
            }
            else
            {
                cur = stk.top();
                stk.pop();
                table.push_back(cur->val);
                cur = cur->right;
            }
        }

        for (int i = 1; i < table.size(); ++i)
        {
            if (table[i] <= table[i - 1])
            {
                return false;
            }
        }

        return true;
    }
};

到了這里，關(guān)于算法刷題Day 20 最大二叉樹+合并二叉樹+二叉搜索樹中的搜索+驗(yàn)證二叉搜索樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！