二叉树的建树

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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]

非递归建树

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]

递归建树

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