算法数据结构

二叉树的建树

字数统计: 1.2k字   |   阅读时长: 5分
, ,

摘要: 本文介绍了一类由给定的递归定义的建树规则进行建树的问题。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

相关的内容：

抽象问题

给出一组数据，和一个递归定义的二叉树建树规则，将给定的数据按照递归定义的规则建成一棵二叉树。

关于递归的问题有很多种类型，此前在文章 递归 中有所总结。这里建树规则是递归定义的，因此这是一种典型的递归的问题，那么按照规则直接递归地建树是个直接的办法，此外也是可以利用栈进行非递归建树的。

题目

654. 最大二叉树

给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：

  1. 二叉树的根是数组 nums 中的最大元素。
  2. 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
  3. 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。

返回有给定数组 nums 构建的 最大二叉树 。

提示：

1
2
3
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同

示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：

  • [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    • [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
      • 空数组，无子节点。
      • [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
        • 空数组，无子节点。
        • 只有一个元素，所以子节点是一个值为 1 的节点。
    • [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
      • 只有一个元素，所以子节点是一个值为 0 的节点。
      • 空数组，无子节点。

示例 2：
输入：nums = [3,2,1]
输出：[3,null,2,null,1]

非递归建树 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.empty()) return nullptr;
        int n = nums.size();
        stack<TreeNode*> st;
        for(int i = 0; i < n; ++i)
        {
            TreeNode *iter = new TreeNode(nums[i]);
            if(st.empty() || st.top() -> val > nums[i])
                st.push(iter);
            else
            {
                TreeNode *st_top = st.top();
                st.pop();
                while(!st.empty() && st.top() -> val < nums[i])
                {
                    st.top() -> right = st_top;
                    st_top = st.top();
                    st.pop();
                }
                iter -> left = st_top;
                st.push(iter);
            }
        }
        TreeNode *result = st.top();
        st.pop();
        while(!st.empty())
        {
            st.top() -> right = result;
            result = st.top();
            st.pop();
        }
        return result;
    }
};

998. 最大二叉树 II

最大树定义：一个树，其中每个节点的值都大于其子树中的任何其他值。

给出最大树的根节点 root。

就像之前的问题那样，给定的树是从列表 A（root = Construct(A)）递归地使用下述 Construct(A) 例程构造的：

  • 如果 A 为空，返回 null
  • 否则，令 A[i] 作为 A 的最大元素。创建一个值为 A[i] 的根节点 root
  • root 的左子树将被构建为 Construct([A[0], A[1], …, A[i-1]])
  • root 的右子树将被构建为 Construct([A[i+1], A[i+2], …, A[A.length - 1]])
  • 返回 root

请注意，我们没有直接给定 A，只有一个根节点 root = Construct(A).

假设 B 是 A 的副本，并在末尾附加值 val。题目数据保证 B 中的值是不同的。

返回 Construct(B)。

提示：

1
1 <= B.length <= 100

示例 1：
输入：root = [4,1,3,null,null,2], val = 5
输出：[5,4,null,1,3,null,null,2]
解释：A = [1,4,2,3], B = [1,4,2,3,5]

示例 2：
输入：root = [5,2,4,null,1], val = 3
输出：[5,2,4,null,1,null,3]
解释：A = [2,1,5,4], B = [2,1,5,4,3]

示例 3：
输入：root = [5,2,3,null,1], val = 4
输出：[5,2,4,null,1,3]
解释：A = [2,1,5,3], B = [2,1,5,3,4]

递归建树 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if(root -> val < val)
        {
            TreeNode *tmp = new TreeNode(val);
            tmp -> left = root;
            return tmp;
        }
        if(!root -> right)
        {
            TreeNode *tmp = new TreeNode(val);
            root -> right = tmp;
            return root;
        }
        TreeNode *prev = root;
        dfs(root -> right, val, prev);
        return root;
    }

private:
    void dfs(TreeNode* root, int val, TreeNode*& prev)
    {
        if(root -> val < val)
        {
            TreeNode *tmp = new TreeNode(val);
            tmp -> left = root;
            prev -> right = tmp;
            return;
        }
        if(!root -> right)
        {
            TreeNode *tmp = new TreeNode(val);
            root -> right = tmp;
            return;
        }
        prev = root;
        dfs(root -> right, val, prev);
    }
};
Share