二叉树的递归构造.md

• 由前中后序遍历构造二叉树
  • 问题分类
  • leetcode.105 从前序与中序遍历序列构造二叉树
  • leetcode.106 从中序与后序遍历序列构造二叉树
• 构造二叉树（一般先构造根节点，再构造左右子树）
  • leetcode.617 合并二叉树
  • leetcode.108 将有序数组转换为二叉搜索树
  • leetcode.654 最大二叉树

---

由前中后序遍历构造二叉树

问题分类

1. 根据前序遍历和中序遍历构造二叉树：前序遍历的头节点一定是根节点，从前序遍历中找到根节点并在中序遍历中找到根节点对应的位置，将中序遍历数组分为两部分。
   设前序遍历数组区间为 $[pl, pr]$，中序遍历数组区间为 $[il, ir]$，设根节点在中序遍历数组中下标为 $t$。 递归终止条件为：$pl > pr$ 逻辑：左儿子根节点为递归前序数组 $[pl+1, t-il+pl]$，对应中序数组 $[il, t-1]$，右儿子根节点为递归前序数组 $[t-il+pl+1, pr-1]$，对应中序数组 $[t+1, ir]$
2. 根据中序遍历和后序遍历构造二叉树：后序遍历的尾节点一定是根节点，从后序遍历中找到根节点并在中序遍历中找到根节点对应的位置，将中序遍历数组分为两部分。
   设前序遍历数组区间为 $[pl, pr]$，中序遍历数组区间为 $[il, ir]$，设根节点在中序遍历数组中下标为 $t$。 递归终止条件为：$pl > pr$ 逻辑：左儿子根节点为递归后序数组 $[pl, t-il+pl-1]$，对应中序数组 $[il, t-1]$，右儿子根节点为递归后序数组 $[t-il+pl, pr-1]$，对应中序数组 $[t+1, ir]$

leetcode.105 从前序与中序遍历序列构造二叉树

• 链接https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
• leetcode解题代码

/**
 * 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:
    unordered_map<int, int> hash;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        // 哈希表记录中序遍历中根节点的位置
        for (int i = 0; i < n; i ++) hash[inorder[i]] = i;
        return build(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir){
        // 递归终止条件
        if (pl > pr) return nullptr;
        // 找到根节点在中序遍历中的下标
        auto t = hash[preorder[pl]];
        // 创建根节点并递归生成左右子树
        auto root = new TreeNode(preorder[pl]);
        root->left = build(preorder, inorder, pl + 1, t - il + pl, il, t - 1);
        root->right = build(preorder, inorder, t - il + pl + 1, pr, t + 1, ir);
        return root;
    }
};

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

• 链接https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
• leetcode解题代码

/**
 * 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:
    unordered_map<int, int> hash;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        for (int i = 0; i < n; i ++) hash[inorder[i]] = i;
        return build(inorder, postorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* build(vector<int>& inorder, vector<int>& postorder, int il, int ir, int pl, int pr){
        if (pl > pr) return nullptr;

        auto t = hash[postorder[pr]];
        auto root = new TreeNode(postorder[pr]);
        root->left = build(inorder, postorder, il, t - 1, pl, t - il + pl - 1);
        root->right = build(inorder, postorder, t + 1, ir, t - il + pl, pr - 1);
        return root;
    }
};

构造二叉树（一般先构造根节点，再构造左右子树）

leetcode.617 合并二叉树

• 链接https://leetcode.cn/problems/merge-two-binary-trees/
• 解题思路：
  递归函数功能：合并 root1 root2 两颗树并返回它们合并后的根节点
  1. 递归终止条件：
     如果树 1 不存在那么合并后的二叉树为树 2
     如果树 2 不存在那么合并后的二叉树为树 1
  2. 递归逻辑：
     先构造根节点，根节点的值为树 1 和树 2 根节点之和
     构造左子树，合并 root1 root2 的左子树，合并后的根节点为 root1->left
     构造右子树，合并 root1 root2 的右子树，合并后的根节点为 root1->right
• leetcode解题代码

/**
 * 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) 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;
    }
};

leetcode.108 将有序数组转换为二叉搜索树

• 链接https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
• 解题思路：二叉搜索树的根节点为有序数组的中点
  递归函数功能：将有序数组 nums 构造为二叉搜索树并返回新树的根节点
  1. 递归终止条件：如果左端点大于右端点则终止递归
  2. 递归逻辑：
     构造根节点，根节点为有序数组的中点
     构造左子树，返回值为左子树的根节点，也就是根节点的左儿子
     构造右子树，返回值为右子树的根节点，也就是根节点的右儿子
• leetcode解题代码

/**
 * 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* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size();
        return build(nums, 0, n - 1);
    }

    TreeNode* build(vector<int>& nums, int l, int r){
        if (l > r) return nullptr;

        int mid = l + r >> 1;
        auto root = new TreeNode(nums[mid]);
        root->left = build(nums, l, mid - 1);
        root->right = build(nums, mid + 1, r);
        return root;
    }
};

leetcode.654 最大二叉树

• 链接https://leetcode.cn/problems/maximum-binary-tree/
• 解题思路：与上一题类似，用双指针算法找到树的根节点
• leetcode解题代码

/**
 * 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) {
        int n = nums.size();
        return build(nums, 0, n - 1);
    }
    
    TreeNode* build(vector<int>& nums, int l, int r){
        if (l > r) return nullptr;
        // 双指针算法，在不改变原数组顺序的情况下找到最大值的下标
        int t = l;
        for (int i = l + 1; i <= r; i ++){
            if (nums[i] > nums[t])
                t = i;
        }

        auto root = new TreeNode(nums[t]);
        root->left = build(nums, l, t - 1);
        root->right = build(nums, t + 1, r);
        return root;
    }
};