合并二叉树

Posted on | In | | reads times

考点：二叉树遍历，二叉树建立，多行输入，数组。
题目描述：
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：
两颗二叉树是:
Tree 1 ：
1
/ \
3 2
/
5

Tree 2：
2
/
1 3
\
4 7

合并后的树为：
3
/
4 5
/ \
5 4 7

输入描述：

第一行输入整数n，m。(分别表示树1和树2的节点数,1<=n，m<=100)
接下来n行，第i行三个整数l,r,v, (0<=l,r<=n , 0<=v<=100) ,表示第一棵树的第i个结点的左儿子编号，右儿子编号和权值。
接下来m行，第i行三个整数l,r,v, (0<=l,r<=n , 0<=v<=100) ,表示第二棵树的第i个结点的左儿子编号，右儿子编号和权值。
（对于左右儿子，如果编号为0表示空。保证如果儿子不为空，则儿子编号大于父亲编号。）

输出描述：

输出合并后树按层遍历的各结点权值，相邻权值之间以一个空格相间。

本题在牛客网的瓜子二手车编程题中出现，首先需要控制输入，输入是由第一行的两个数字决定接下来输入的行数。所以需要首先js的多行输入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var readline=require('readline')
const r1=readline.createInterface({
	input:process.stdin,
	output:process.stdout
})
var linesArrayIndex=0;
var linesArray=[];
var resultArray=[];
r1.on('line',function(line){
	if(linesArrayIndex==0){
		var length=line.split(' ');
		var n1=length[0];
		var n2=length[1];
		linesArray[linesArrayIndex]=n1+n2;
		//首行加入输入流队列，并表示接下来的输入行数。
	}else{
		linesArray[linesArrayIndex]=line;
		resultArray.push(line);
	}
	linesArrayIndex++;
	if(resultArray.length==n1+n2){
		///之后对结果数组进行的操作
	}
})

此时得到的输入数组是

[‘2 3 1’,’4 0 3’,’0 0 2’,’0 0 5’,’2 3 2’,’0 4 1’,’0 5 3’,’0 0 4’,’0 0 7’]

需要将这一整个数组根据两个节点个数n1和n2分割，并转换成二叉树的数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function stringtonumberarr(array){
 	let newarr=[];
    for(let i of array){
        let temparr=i.split(' ');
        var newtemp=[];
        for(let j of temparr){
            j=parseInt(j);
            newtemp.push(j);
        }
        newarr.push(newtemp)
    }
    return newarr;
}
let arr1=[];
let arr2=[];
for(let i=0;i<n1;i++){
    arr1.push(resultArray[i]);
}
let arrone=stringtonumberarr(arr1);
for(let i=0;i<n2;i++){
    arr2.push(resultArray[i+n1]);
}
let arrtwo=stringtonumberarr(arr2);

经过以上转换，数组元素不再为字符串而是数值型。

将处理过的数组转换为二叉树。

[ [2 ,3 ,1], [4 ,0 ,3], [0 ,0 ,2], [0 ,0 ,5] ]

我的想法是，假设数组为arr，arr[0][0]如果不为0，则表示该节点有左孩子，同理可知是否有右孩子。
将左右标记为true，若为0则为null。
然后再将节点连接，通过编号对应数组下标，找到对应的父子节点然后连接。

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
var inittree = function (arr) {
    var pRoot=new Node(arr[0][2]);
    // console.log(pRoot)
    if(arr[0][0]>0){
        pRoot.left=true;
    }
    if(arr[0][1]>0){
        pRoot.right=true;
    }
    var nodearr=[];
    nodearr.push(pRoot);
    for (let i = 1; i < arr.length; i++) {
        var node =new Node(arr[i][2]);
        if(arr[i][0]>0){
            node.left=true;
        }
        if(arr[i][1]>0){
            node.right=true;
        }
        nodearr.push(node)
    }
      for (let j = 0; j < nodearr.length;j++) {
        if(arr[j][0]!=0){
            nodearr[j].left=nodearr[arr[j][0]-1]
        }
        if(arr[j][1]!=0){
            nodearr[j].right=nodearr[arr[j][1]-1];
        }
    }
    // console.log(pRoot)
    return pRoot;
}

将两个数组转换成二叉树之后，进行二叉树合并，合并二叉树的思想是递归。思路是新建一棵树。

  1. 首先用两个指针同时指向两棵树的树根，然后从看是否都存在，若都存在，新建节点，其值为两个节点权值之和。若只有其中一个节点存在，则直接赋值然后连接。
  2. 结束该节点后再看该节点的左节点，然后再看右节点。
  3. 重复2步骤，进行递归。若到叶子节点则返回null，最外层返回根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function mergetree(pRoot1,pRoot2){
    var temp;
    if(pRoot1!=null&&pRoot2!=null){
        temp=new Node(pRoot1.val+pRoot2.val);
        temp.left=mergetree(pRoot1.left,pRoot2.left);
        temp.right=mergetree(pRoot1.right,pRoot2.right);
    }else if(pRoot1==null&&pRoot2!=null){
        temp=pRoot2;
    }else if(pRoot1!=null&&pRoot2==null){
        temp=pRoot1;
    }else{
        return null;
    }
    //console.log(temp)
    return temp;
}

最后题目要求需要按层遍历输出结果
此处用的是非递归实现的按层遍历，需要用一个队列来放入每一层的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function leveltraver(pRoot) {
    var result=[];
    var tree=[];
    tree.push(pRoot);
    while(tree.length){
        var node=tree.shift();
        result.push(node.val);
        if(node.left!=null){
            tree.push(node.left);
        }
        if(node.right!=null){
            tree.push(node.right);
        }
    }
    return result;
}

最后是完整代码：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
var readline=require('readline');
const r1=readline.createInterface({
    input:process.stdin,
    output:process.stdout
})
var Node = function(val){
    this.left=null;
    this.right=null;
    this.val=val;
}
function mergetree(pRoot1,pRoot2){
    var temp;
    if(pRoot1!=null&&pRoot2!=null){
        temp=new Node(pRoot1.val+pRoot2.val);
        temp.left=mergetree(pRoot1.left,pRoot2.left);
        temp.right=mergetree(pRoot1.right,pRoot2.right);
    }else if(pRoot1==null&&pRoot2!=null){
        temp=pRoot2;
    }else if(pRoot1!=null&&pRoot2==null){
        temp=pRoot1;
    }else{
        return null;
    }
    //console.log(temp)
    return temp;
}
var inittree = function (arr) {
    var pRoot=new Node(arr[0][2]);
    // console.log(pRoot)
    if(arr[0][0]>0){
        pRoot.left=true;
    }
    if(arr[0][1]>0){
        pRoot.right=true;
    }
    var nodearr=[];
    nodearr.push(pRoot);
    for (let i = 1; i < arr.length; i++) {
        var node =new Node(arr[i][2]);
        if(arr[i][0]>0){
            node.left=true;
        }
        if(arr[i][1]>0){
            node.right=true;
        }
        nodearr.push(node)
    }
      for (let j = 0; j < nodearr.length;j++) {
        if(arr[j][0]!=0){
            nodearr[j].left=nodearr[arr[j][0]-1]
        }
        if(arr[j][1]!=0){
            nodearr[j].right=nodearr[arr[j][1]-1];
        }
    }
    // console.log(pRoot)
    return pRoot;
}
function stringtonumberarr(array){
    let newarr=[];
    for(let i of array){
        let temparr=i.split(' ');
        var newtemp=[];
        for(let j of temparr){
            j=parseInt(j);
            newtemp.push(j);
        }
        newarr.push(newtemp)
    }
    return newarr;
}
function leveltraver(pRoot) {
    var result=[];
    var tree=[];
    tree.push(pRoot);
    while(tree.length){
        var node=tree.shift();
        result.push(node.val);
        if(node.left!=null){
            tree.push(node.left);
        }
        if(node.right!=null){
            tree.push(node.right);
        }
    }
    return result;
}
var linesArray=[];
 
var linesArrayIndex=0;
 
var resultArray=[];
var n1,n2;
r1.on('line',function(line){
   if(linesArrayIndex==0){
       var length=line.split(' ');
       n1=parseInt(length[0]);
       n2=parseInt(length[1]);
       linesArray[linesArrayIndex]=Number(length[0])+Number(length[1]);
   }else{
       linesArray[linesArrayIndex]=line;
   }
     
    linesArrayIndex++;
      for(var i in linesArray.slice(1)){
        resultArray[i]=linesArray.slice(1)[i];
    }
     
     if(resultArray.length==linesArray[0]){
        //打印输出整合在数组resultArray中的输入内容
        let arr1=[];
        let arr2=[];
        for(let i=0;i<n1;i++){
            arr1.push(resultArray[i]);
        }
        let arrone=stringtonumberarr(arr1);
        for(let i=0;i<n2;i++){
            arr2.push(resultArray[i+n1]);
        }
        let arrtwo=stringtonumberarr(arr2);
                
       //console.log(arrone)
       //console.log(arrtwo)
       var pRoot1 = inittree(arrone);
       var pRoot2 = inittree(arrtwo);
 
       var resroot=mergetree(pRoot1,pRoot2);
       var ans=leveltraver(resroot);
       console.log(ans.join(' '))
        r1.close();
    }
})