逐层构造二叉树

刷leetcode时,测试用例输入一般都是一个元组,而二叉树的输入是按照元组顺序从上到下、从左到右逐层构造的。

为了方便本地测试,现在来实现这一构造方式吧!

首先二叉树数据结构定义:

1
2
3
4
5
6
7
8
9
10
struct TreeNode {
public:
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) {}
};

1. 用整数数组构造一个满二叉树

首先,我们先看一个以整数数组[0,1,2,3,4,5,6,7,8,9,10,11]构造的满二叉树的结构:

graph TB
0((0))
0 --> 1((1))
0 --> 2((2))
1 --> 3((3))
1 --> 4((4))
2 --> 5((5))
2 --> 6((6))
3 --> 7((7))
3 --> 8((8))
4 --> 9((9))
4 --> 10((10))
5 --> 11((11))

注意,上图中圆圈中的值同样对应数组的下标,不论数组的值怎么变,数组下标在树中的位置不变。

由此可知,在构造该二叉树时:

1. 节点的左子树顶点序号是奇数
2. 节点的右子树顶点序号是偶数
3. 根节点序号与子节点的序号的关系:root = (n - 1) / 2,比如子节点(5,6)对应根节点是2。

编程的思路与广度优先遍历类似

广度优先遍历的思路是:创建一个容器保存需要遍历的节点,当访问到该节点时,将它的左右子节点加入容器。

广度优先遍历步骤以上图举例:

  1. 首先将根节点0加入容器;

  2. 访问容器,输出节点0,将节点0的左右子节点1、2加入容器(若子节点为空则不添加);

  3. 继续访问容器,输出节点1,将1的左右子节点3、4加入容器;

  4. 继续访问容器,输出节点2,将2的左右子节点5、6加入容器;

  5. 重复直到访问完容器中每一个节点。

逐层构造步骤:

  1. 创建一个节点并加入容器,若该节点为第一个创建的节点,作为二叉树的根节点;
  2. 创建一个节点并加入容器,找到父节点指向该节点(从根节点开始构造,树的所有节点都保存在容器中);
  3. 父节点序号:root = (n - 1) / 2
  4. 子节点序号:奇数则是左子节点,偶数则是右子节点;
  5. 重复直到构造完列表中的数。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
TreeNode* biTreeInit(vector<int>vi) {
int n = vi.size();
if (n == 0) return NULL;
vector<TreeNode*>vt; //保存节点的容器

TreeNode* node; //根节点
TreeNode* t; //临时节点
node = NULL;

int i = 0;
int root = 0;
while (i < n) {
t = new TreeNode(vi[i]);
vt.push_back(t); //每一个创建的节点都将加入容器
if (i == 0) node = t; //保存根节点

if (i % 2 == 1) vt[root]->left = t; //奇数对应左子树
else vt[root]->right = t; //偶数对应右子树

i++;
root = (i - 1) / 2; //根据子序号获得父序号
}
return node;
};

2.字符串数组构造二叉树,其中null表示空节点

方法与1.整数数组构造相似,区别是:

  1. 将字符串转化为整数;

  2. 如果节点为空节点,则不加入容器;

先看一个由字符串数组["0","1","2","3","null","5","null","7","8","9","10","11"]构造的二叉树:

graph TB
0((0-0))
0 --> 1((1-1))
0 --> 2((2-2))
1 --> 3((3-3))
1 --> a((null-4))
2 --> 5((5-5))
2 --> b((null-6))
3 --> 7((7-7))
3 --> 8((8-8))
5 --> 9((9-9))
5 --> 10((10-10))
7 --> 11((11-11))

图中,“-”前的值表示字符串对应的数值,“-”后的值为对应的数组下标。

节点null实际并不存在,只是为了便于观察数组与树的关系而画出来了。

根据1.整数数组构造的思路,我们在构造过程中会逐步将每个节点的序号加入容器,最后得到的容器为[0,1,2,3,4,5,6,7,8,9,10,11],其中[4,6]对应空节点。

观察上图,我们发现:

1. 子树顶点序号的奇偶特点并未发生改变;
2. 根节点前每多出 x 个空节点,根节点序号与子树序号的关系:root = (n - 1) / 2root要多 x;

若将空节点的序号加入容器,则根据子节点序号计算根节点序号的方式就复杂许多,而若我们不将空节点加入容器,则最后得到的容器为[0,1,2,3,5,7,8,9,10,11]

graph TB
0((0-0))
0 --> 1((1-1))
0 --> 2((2-2))
1 --> 3((3-3))
1 --> a((null))
2 --> 5((5-4))
2 --> b((null))
3 --> 7((7-5))
3 --> 8((8-6))
5 --> 9((9-7))
5 --> 10((10-8))
7 --> 11((11-9))

根据root = (n - 1) / 2对二叉树的节点验证:

对节点(9,10)计算得到4,容器下标4对应的节点为5,是(9,10)的根节点,符合。

对节点(11)计算得到5,容器下标5对应的节点为7,是(11)的根节点,符合。

因此在不将空节点加入容器时,不需要改变表达式就能正确构造。

观察树图,由于空节点并没有子节点,因此字符串数组中空节点的子节点位置被后面的节点占据。如果空节点不加入容器,空节点位置被后面节点占据,则空节点后面的根节点与它们的子节点的关系恰好不变。

代码如下:

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
TreeNode* biTreeInit(vector<string>vs) {
int n = vs.size();
if (n == 0) return NULL;
vector<TreeNode*>vt; //保存节点的容器

TreeNode* node; //根节点
TreeNode* t; //临时节点
node = NULL;

int i = 0;
int root = 0;
while (i < n) {
t = NULL;
if (vs[i] != "null") {
int t_i = atoi(vs[i].c_str());
t = new TreeNode(t_i);
vt.push_back(t); //每一个创建的节点都将加入容器
}
if (i == 0) node = t; //保存根节点

if (i % 2 == 1) vt[root]->left = t; //奇数对应左子树
else vt[root]->right = t; //偶数对应右子树

i++;
root = (i - 1) / 2; //根据子序号获得父序号
}
return node;
};