二叉树 – 建二叉树问题

1 算法模版

• 1 递归返回值为TreeNode *
• 2 建立根节点
• 3 获取左子树（调用递归）
• 4 获取右子树（调用递归）
• 5 返回根节点

2 真题演练

2.1 106.从中序与后序遍历序列构造二叉树

class Solution {
public:
    TreeNode* traversal(vector& inorder, vector& postorder){
        // 1 判空
        if(postorder.size() == 0) return nullptr;

        // 2 去后序数组中根节点
        int rootValue = postorder[postorder.size()-1];
        TreeNode* root = new TreeNode(rootValue);

        // 3 判断是否只有一个节点
        if (postorder.size() == 1) return root;

        // 4 找到中序数组的切割点
        int delimiterIndex;
        for(delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++){
            if (inorder[delimiterIndex] == rootValue) break;
        }

        // 5 对中序数组进行切割
        vector leftInorder(inorder.begin(), inorder.begin()+delimiterIndex);
        vector rightInorder(inorder.begin()+delimiterIndex+1, inorder.end());
        // postorder.resize(postorder.size()-1);

        // 6 对后序数组进行切割
        vector leftPostorder(postorder.begin(), postorder.begin()+leftInorder.size());
        vector rightPostorder(postorder.begin()+leftInorder.size(), postorder.end()-1);
        
        // 7 递归
        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);
        return root;
    }

    TreeNode* buildTree(vector& inorder, vector& postorder) {
        if (inorder.size()==0 || postorder.size()==0) return nullptr;
        return traversal(inorder, postorder);
    }
};

2.2 654.最大二叉树

class Solution {
public:
    TreeNode* traversal(vector& nums){
        if (nums.size() == 0) return nullptr;
        // 1 找到最大值与下标，并创建root节点
        int rootIndex, rootValue=INT_MIN;
        for(int i = 0; i < nums.size(); i++){
            if (rootValue < nums[i]){
                rootValue = nums[i];
                rootIndex = i;
            }
        }
        TreeNode* root = new TreeNode(rootValue);

        // 2 找到左子数组和右子数组
        vector leftNums(nums.begin(), nums.begin()+rootIndex);
        vector rightNums(nums.begin()+rootIndex+1, nums.end());

        // 3 递归左子树
        root->left = traversal(leftNums);
        // 4 递归右子树
        root->right = traversal(rightNums);

        return root;
    }

    TreeNode* constructMaximumBinaryTree(vector& nums) {
        return traversal(nums);
    }
};

2.3 617.合并二叉树

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