逐层构造二叉树
逐层构造二叉树
刷leetcode时,测试用例输入一般都是一个元组,而二叉树的输入是按照元组顺序从上到下、从左到右逐层构造的。
为了方便本地测试,现在来实现这一构造方式吧!
首先二叉树数据结构定义:
1 | struct TreeNode { |
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。
编程的思路与广度优先遍历类似
广度优先遍历的思路是:创建一个容器保存需要遍历的节点,当访问到该节点时,将它的左右子节点加入容器。
广度优先遍历步骤以上图举例:
首先将根节点0加入容器;
访问容器,输出节点0,将节点0的左右子节点1、2加入容器(若子节点为空则不添加);
继续访问容器,输出节点1,将1的左右子节点3、4加入容器;
继续访问容器,输出节点2,将2的左右子节点5、6加入容器;
重复直到访问完容器中每一个节点。
逐层构造步骤:
- 创建一个节点并加入容器,若该节点为第一个创建的节点,作为二叉树的根节点;
- 创建一个节点并加入容器,找到父节点指向该节点(从根节点开始构造,树的所有节点都保存在容器中);
- 父节点序号:
root = (n - 1) / 2
; - 子节点序号:奇数则是左子节点,偶数则是右子节点;
- 重复直到构造完列表中的数。
代码如下:
1 | TreeNode* biTreeInit(vector<int>vi) { |
2.字符串数组构造二叉树,其中null表示空节点
方法与1.整数数组构造相似,区别是:
将字符串转化为整数;
如果节点为空节点,则不加入容器;
先看一个由字符串数组["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) / 2
,root
要多 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 | TreeNode* biTreeInit(vector<string>vs) { |