代码随想录1016-Day17

654.最大二叉树

文章链接:代码随想录
题目链接：题目

思路：先要找到根节点，然后让 build 函数递归生成左右子树即可。

    
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }
    TreeNode* build(vector<int>nums, int l, int r)
    {
        if(l > r) return nullptr;
        int index = -1, max = INT_MIN;
        for (int i = l; i <= r; i++)
        {
            if(nums[i] > max)
            {
                max = nums[i];
                index = i;            
                }
        }
        TreeNode *root = new TreeNode(max);
        root->left = build(nums, l, index - 1);
        root->right = build(nums, index + 1, r);
        return root;
    }
};

700.二叉搜索树中的搜索

文章链接:代码随想录
题目链接：题目

思路：
利用 BST 左小右大的特性，可以避免搜索整棵二叉树去寻找元素，从而提升效率。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
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->left, val);
        }
        if(root->val < val)
        {
            return searchBST(root->right, val);
        }
        return root;
    }
};

617.合并二叉树

文章链接:代码随想录
题目链接：题目

思路：
可以看做是在遍历 root1 这一棵二叉树，顺便把 root2 的节点合并过来。
也可以创建一个新节点接收roo1->val + root2->val

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1 && !root2) return nullptr;
        if(!root1) return root2;
        if(!root2) return root1;
        TreeNode *root = new TreeNode(root1->val + root2->val);
        root->left = mergeTrees(root1->left, root2->left);
        root->right = mergeTrees(root1->right, root2->right);
        return root;
    }
};

总结

二叉树解题的思维模式分两类：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

收获

补之前的卡 又做了一遍