Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

求两棵树的第一个交点

首先判断两棵树是否相交,可以根据判断两个链表是否相交扩展而来,如果相交的话,将第1个链表的末尾指向第1个链表的头部将会成环,因此借鉴这种思路

自己的思路如下:KlYSSU

验证两棵树是否相交

思路:Morris先序遍历,遍历第1棵树的时候将叶节点的左指针指向root1,然后遍历root2,如果发现某一个节点左指针指向第1个树根,说明相交,包含了两个树中有一个是子树的情况

时间复杂度:O(N)
空间复杂度:O(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
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
//判断两个树是否相交
//采用Morris先序遍历可以在时间复杂度不变的情况下将空间复杂度将为O(1)
func ifIntersection(root1, root2 *TreeNode) bool {
//有一个为空,说明不相交
if root1 == nil || root2 == nil {
return false
}

//Morris先序遍历树1:第一个树的叶子节点的左指针指向第一个树根
var prev *TreeNode
cur := root1
for cur != nil {
if cur.Left == nil && cur.Right == nil {
cur.Left, cur = root1, cur.Right
} else if cur.Left == root1 {
cur = cur.Right
} else {
prev = cur.Left
for (prev.Right != nil) && (prev.Right != cur) { //找到左子树的最右节点
prev = prev.Right
}
//如果最右节点的左子树为空,则指向root1
if prev.Left == nil {
prev.Left = root1
}

if prev.Right == nil { //找到了最右节点
prev.Right = cur
cur = cur.Left
} else { //此时就是最右节点,只不过此时最右节点的右指针指向的不是nil,所以要置nil
prev.Right = nil
cur = cur.Right
}
}
}
//Morris先序遍历树2:如果遍历的时候发现左指针指向第1个树根,说明相交
cur, prev = root2, nil
var ret bool
for cur != nil {
if cur.Left == root1 {
ret, cur.Left = true, nil
} else if cur.Left == nil {
//如果当前节点是叶子节点
if cur.Right == nil {
cur.Left = nil
}
cur = cur.Right
} else {
prev = cur.Left
for (prev.Right != nil) && (prev.Right != cur) { //找到左子树的最右节点
prev = prev.Right
}
if prev.Left == root1 {
prev.Left = nil
ret = true
}

if prev.Right == nil { //找到了最右节点
//判断是否为叶子节点
if prev.Left == root1 {
prev.Left = nil
ret = true
}
prev.Right = cur
cur = cur.Left
} else { //此时就是最右节点,只不过此时最右节点的右指针指向的不是nil,所以要置nil
prev.Right = nil
cur = cur.Right
}
}
}

return ret
}

求出两棵树相交的第一个交点

最优解法:

思路:

  1. Morris先序遍历树1,如果是非叶节点加入到哈希表中,如果是叶子节点将左指针指向树1的根
  2. Morris先序遍历树2,如果遍历到某个非叶节点发现已经在哈希表中,直接返回该节点,如果遍历到叶子节点的时候发现左指针指向树1的跟,直接返回该节点

时间复杂度:O(N)
空间复杂度:O(m) m为非叶节点的个数

最优解法
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
//方法二:找到两个相交树的第一个交点
//按照群里老哥提供的解法:(使用morris遍历不需要借助任何数组)遍历到第1个树,如果是非叶子节点,则加入到我们的哈希表,如果是叶子节点,则左指针指向我们的根
//返回是否相交,以及相交的第一个节点(如果第一个相交的点在叶节点上是不需要借助哈希表的,但是如果在非叶节点上相交是需要借助哈希表的)
//改正中
func SolutionII(root1, root2 *TreeNode) (bool, *TreeNode) {
//判断是否相交的过程中找到第一个相交的节点
//有一个为空,说明不相交
if root1 == nil || root2 == nil {
return false, nil
}

var ifIntersection bool
var intersectionNode *TreeNode

hashmap := make(map[*TreeNode]bool)

//Morris先序遍历树1:第一个树的叶子节点的左指针指向第一个树根
var mostRight *TreeNode
cur := root1
for cur != nil {

//如果当前节点没有左子树
if cur.Left == nil { //当前节点向右移动 (只有没有左子树的节点会走这一步)
if cur.Right == nil {
cur.Left = root1
}
hashmap[cur] = true
cur = cur.Right
} else if cur.Left == root1 {
cur = cur.Right
} else { //找到当前节点左子树的最右节点
mostRight = cur.Left
for mostRight.Right != nil && mostRight.Right != cur {
mostRight = mostRight.Right
}
//此时mostRight就是当前节点左子树的最右节点
if mostRight.Right == nil { //说明是第一次来到
//加入到我们的哈希表,因为不是叶节点
hashmap[cur] = true
mostRight.Right, cur = cur, cur.Left
} else { //说明是第二次来到(只有有左子树的时候才会有第二次来到)
mostRight.Right, cur = nil, cur.Right
}
}
}
//遍历完之后,只有叶子节点的左指针都指向root1并且所有节点都加入到我们的hashmap中
//Morris先序遍历树2:如果遍历的时候发现左指针指向第1个树根,说明相交
cur, mostRight = root2, nil
for cur != nil {

//如果当前节点的左子树为root1
if cur.Left == root1 || cur.Left == nil{ //叶 || 有右的非叶
if _, ok := hashmap[cur]; ok && intersectionNode == nil {
ifIntersection, intersectionNode = true, cur
}
cur = cur.Right
} else { //找到当前节点左子树的最右节点
mostRight = cur.Left
for mostRight.Right != nil && mostRight.Right != cur {
mostRight = mostRight.Right
}
//此时mostRight就是当前节点左子树的最右节点
if mostRight.Right == nil { //说明是第一次来到
if _, ok := hashmap[cur]; ok && intersectionNode == nil {
ifIntersection, intersectionNode = true, cur
}
mostRight.Right, cur = cur, cur.Left
} else { //说明是第二次来到(只有有左子树的时候才会有第二次来到)
mostRight.Right, cur = nil, cur.Right
}
}
}
return ifIntersection, intersectionNode
}

暴力解法

思路:

  1. 时间复杂度:O(N)
  2. 空间复杂度:O(N)
暴力解法
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
//暴力:使用哈希表
//方法一:暴力解法,使用哈希表将树1层次遍历的结果保存到我们的哈希表中,然后遍历树2,如果节点出现在哈希表中就返回该节点
func SolutionI(root1, root2 *TreeNode) *TreeNode {
//有一个为空就直接返回nil
if root1 == nil || root2 == nil {
return nil
}

hashmap := make(map[*TreeNode]bool)
queue := []*TreeNode{root1}
for len(queue) != 0 {
node := queue[0]
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}

//注意:遍历的时候一定要将节点加入进去
hashmap[node] = true
queue = queue[1:]
}

//然后遍历树2
queue = append(queue, root2)
for len(queue) != 0 {
node := queue[0]

//遍历树2的时候,如果有一个节点已经在我们的哈希表中,直接返回结果
if _, ok := hashmap[node]; ok {
fmt.Println(node.Val)
return node
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
queue = queue[1:]
}

return nil
}

最后完整代码如下

最后完整代码
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
package main

import "fmt"

/**
* @Author: yirufeng
* @Date: 2021/11/27 6:43 下午
* @Email: yirufeng@foxmail.com
* @GitHub: https://www.github.com/sivanWu0222
* @Desc: 这里写的是一个二叉树的交点,多叉树直接使用哈希表
**/

type TreeNode struct {
Val int
Left, Right *TreeNode
}

//判断两个树是否相交
//采用Morris先序遍历可以在时间复杂度不变的情况下将空间复杂度将为O(1)
func ifIntersection(root1, root2 *TreeNode) bool {
//有一个为空,说明不相交
if root1 == nil || root2 == nil {
return false
}

//Morris先序遍历树1:第一个树的叶子节点的左指针指向第一个树根
var prev *TreeNode
cur := root1
for cur != nil {
if cur.Left == nil && cur.Right == nil {
cur.Left, cur = root1, cur.Right
} else if cur.Left == root1 {
cur = cur.Right
} else {
prev = cur.Left
for (prev.Right != nil) && (prev.Right != cur) { //找到左子树的最右节点
prev = prev.Right
}
//如果最右节点的左子树为空,则指向root1
if prev.Left == nil {
prev.Left = root1
}

if prev.Right == nil { //找到了最右节点
prev.Right = cur
cur = cur.Left
} else { //此时就是最右节点,只不过此时最右节点的右指针指向的不是nil,所以要置nil
prev.Right = nil
cur = cur.Right
}
}
}
//Morris先序遍历树2:如果遍历的时候发现左指针指向第1个树根,说明相交
cur, prev = root2, nil
var ret bool
for cur != nil {
if cur.Left == root1 {
ret, cur.Left = true, nil
} else if cur.Left == nil {
//如果当前节点是叶子节点
if cur.Right == nil {
cur.Left = nil
}
cur = cur.Right
} else {
prev = cur.Left
for (prev.Right != nil) && (prev.Right != cur) { //找到左子树的最右节点
prev = prev.Right
}
if prev.Left == root1 {
prev.Left = nil
ret = true
}

if prev.Right == nil { //找到了最右节点
//判断是否为叶子节点
if prev.Left == root1 {
prev.Left = nil
ret = true
}
prev.Right = cur
cur = cur.Left
} else { //此时就是最右节点,只不过此时最右节点的右指针指向的不是nil,所以要置nil
prev.Right = nil
cur = cur.Right
}
}
}

return ret
}

//暴力:使用哈希表
//方法一:暴力解法,使用哈希表将树1层次遍历的结果保存到我们的哈希表中,然后遍历树2,如果节点出现在哈希表中就返回该节点
func SolutionI(root1, root2 *TreeNode) *TreeNode {
//有一个为空就直接返回nil
if root1 == nil || root2 == nil {
return nil
}

hashmap := make(map[*TreeNode]bool)
queue := []*TreeNode{root1}
for len(queue) != 0 {
node := queue[0]
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}

//注意:遍历的时候一定要将节点加入进去
hashmap[node] = true
queue = queue[1:]
}

//然后遍历树2
queue = append(queue, root2)
for len(queue) != 0 {
node := queue[0]

//遍历树2的时候,如果有一个节点已经在我们的哈希表中,直接返回结果
if _, ok := hashmap[node]; ok {
fmt.Println(node.Val)
return node
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
queue = queue[1:]
}

return nil
}

//方法二:找到两个相交树的第一个交点
//按照群里老哥提供的解法:(使用morris遍历不需要借助任何数组)遍历到第1个树,如果是非叶子节点,则加入到我们的哈希表,如果是叶子节点,则左指针指向我们的根
//返回是否相交,以及相交的第一个节点(如果第一个相交的点在叶节点上是不需要借助哈希表的,但是如果在非叶节点上相交是需要借助哈希表的)
//改正中
func SolutionII(root1, root2 *TreeNode) (bool, *TreeNode) {
//判断是否相交的过程中找到第一个相交的节点
//有一个为空,说明不相交
if root1 == nil || root2 == nil {
return false, nil
}

var ifIntersection bool
var intersectionNode *TreeNode

hashmap := make(map[*TreeNode]bool)

//Morris先序遍历树1:第一个树的叶子节点的左指针指向第一个树根
var mostRight *TreeNode
cur := root1
for cur != nil {

//如果当前节点没有左子树
if cur.Left == nil { //当前节点向右移动 (只有没有左子树的节点会走这一步)
if cur.Right == nil {
cur.Left = root1
}
hashmap[cur] = true
cur = cur.Right
} else if cur.Left == root1 {
cur = cur.Right
} else { //找到当前节点左子树的最右节点
mostRight = cur.Left
for mostRight.Right != nil && mostRight.Right != cur {
mostRight = mostRight.Right
}
//此时mostRight就是当前节点左子树的最右节点
if mostRight.Right == nil { //说明是第一次来到
//加入到我们的哈希表,因为不是叶节点
hashmap[cur] = true
mostRight.Right, cur = cur, cur.Left
} else { //说明是第二次来到(只有有左子树的时候才会有第二次来到)
mostRight.Right, cur = nil, cur.Right
}
}
}
//遍历完之后,只有叶子节点的左指针都指向root1并且所有节点都加入到我们的hashmap中
//Morris先序遍历树2:如果遍历的时候发现左指针指向第1个树根,说明相交
cur, mostRight = root2, nil
for cur != nil {

//如果当前节点的左子树为root1
if cur.Left == root1 || cur.Left == nil{ //叶 || 有右的非叶
if _, ok := hashmap[cur]; ok && intersectionNode == nil {
ifIntersection, intersectionNode = true, cur
}
cur = cur.Right
} else { //找到当前节点左子树的最右节点
mostRight = cur.Left
for mostRight.Right != nil && mostRight.Right != cur {
mostRight = mostRight.Right
}
//此时mostRight就是当前节点左子树的最右节点
if mostRight.Right == nil { //说明是第一次来到
if _, ok := hashmap[cur]; ok && intersectionNode == nil {
ifIntersection, intersectionNode = true, cur
}
mostRight.Right, cur = cur, cur.Left
} else { //说明是第二次来到(只有有左子树的时候才会有第二次来到)
mostRight.Right, cur = nil, cur.Right
}
}
}
return ifIntersection, intersectionNode
}

func main() {
var root1, root2 *TreeNode
//不相交
root1, root2 = &TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 3}}, &TreeNode{Val: 4, Left: &TreeNode{Val: 5, Left: &TreeNode{Val: 7}, Right: &TreeNode{Val: 8}}, Right: &TreeNode{Val: 6, Left: &TreeNode{Val: 9}, Right: &TreeNode{Val: 10}}}
fmt.Println(ifIntersection(root1, root2)) //false
fmt.Println(SolutionII(root1, root2)) //false
//一个树不是另一个树的子树并且相交于叶节点
node := &TreeNode{Val: 5}
root1, root2 = &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}, Right: node}, Right: &TreeNode{Val: 3}}, &TreeNode{Val: 6, Left: node, Right: &TreeNode{Val: 7}}
fmt.Println(ifIntersection(root1, root2))
fmt.Println(SolutionII(root1, root2))
//一个树不是另一个树的子树并且相交于非叶子节点
node = &TreeNode{Val: 3, Left: &TreeNode{Val: 6}, Right: &TreeNode{Val: 7}}
root1, root2 = &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}, Right: &TreeNode{Val: 5}}, Right: node}, &TreeNode{Val: 8, Left: node, Right: &TreeNode{Val: 9}}
fmt.Println(ifIntersection(root1, root2))
fmt.Println(SolutionII(root1, root2))
//一个树是另一个树的子树
node = &TreeNode{Val: 3, Left: &TreeNode{Val: 6}, Right: &TreeNode{Val: 7}}
root1, root2 = &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}, Right: &TreeNode{Val: 5}}, Right: node}, node
fmt.Println(ifIntersection(root1, root2))
fmt.Println(SolutionII(root1, root2))
}

[最优解] 只需要3次遍历 + 空间复杂度为O(公共子树的根所在路径)的解法

思路:

  1. 第一次遍历:将我们A树所有的叶子节点都指向A的根
  2. 第二次遍历:遍历B树从根到叶子的路径,当遍历到叶子的时候如果发现左指针指向A,直接将该路径保存然后直接退出
  3. 第三次遍历:递归先序遍历树A,遍历的时候如果发现当前遍历到的节点已经在哈希表里面了,此时说明我们已经找到了公共子树的根节点,所以直接返回
验证两棵树是否相交代码
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
type TreeNode struct {
Val int
Left, Right *TreeNode
}

//todo:基于递归的三次遍历
//todo: 第1次遍历,遍历之后,root1所有叶节点的左子树都指向root1
func firstPreorderTraverse(root, cur *TreeNode) {
//避免修改指针之后死循环
if cur == nil || cur.Left == root {
return
}

//如果是叶子就让left指向root
if cur.Left == nil && cur.Right == nil {
cur.Left = root
}

firstPreorderTraverse(root, cur.Left)
firstPreorderTraverse(root, cur.Right)
}

//todo: 第2次遍历,遍历之后,root2中一旦有一个路径的最后一个叶子节点是指向root1的就保存到hashmap中
//返回的bool值表示map是否存储我们想要的路径
func secondPreorderTraverse(cur, target *TreeNode, hashmap map[*TreeNode]bool) (stop bool) {
if cur == nil {
return
}
hashmap[cur] = true

if cur.Left == target {
stop = true
return
}

//如果左右子树有一个可以停止直接返回
if secondPreorderTraverse(cur.Left, target, hashmap) || secondPreorderTraverse(cur.Right, target, hashmap) {
return
}
//否则删除我们路径的节点
delete(hashmap, cur)
return false
}

//todo:第3次遍历。遍历root1,发现某个节点最先出现在hashmap的时候就说明ok,然后返回值
func thirdPreorderTraverse(root, cur *TreeNode, hashmap map[*TreeNode]bool) (bool, *TreeNode) {
if cur == nil {
return false, nil
}

//说明此时就是第一个公共节点,直接返回
if _, ok := hashmap[cur]; ok {
return true, cur
}

//避免死循环,必须写在确认hashmap中有没有下面
//因为有时候某一个叶子节点的Left被我们指向了root
if cur.Left == root { //避免死循环
return false, nil
}

//如果左子树有返回公共节点,直接退出
if ok, node := thirdPreorderTraverse(root, cur.Left, hashmap); ok {
return ok, node
}

//如果有子树有返回公共节点,直接退出
if ok, node := thirdPreorderTraverse(root, cur.Right, hashmap); ok {
return ok, node
}

return false, nil
}

func GetIntersectionTreeRootWithRecursionII(root1, root2 *TreeNode) (bool, *TreeNode) {
if root1 == nil || root2 == nil {
return false, nil
}

//todo: 第1次遍历,遍历之后,root1所有叶节点的左子树都指向root1
firstPreorderTraverse(root1, root1)
//todo: 第2次遍历,遍历之后,root2中一旦有一个路径的最后一个叶子节点是指向root1的就保存到hashmap中
hashmap := make(map[*TreeNode]bool)
secondPreorderTraverse(root2, root1, hashmap)
//todo:第3次遍历。遍历root1,发现某个节点最先出现在hashmap的时候就说明ok,然后返回值
return thirdPreorderTraverse(root1, root1, hashmap)
}

func main() {
var root1, root2 *TreeNode
//不相交
fmt.Println("---------------不相交:---------------")
root1, root2 = &TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 3}}, &TreeNode{Val: 4, Left: &TreeNode{Val: 5, Left: &TreeNode{Val: 7}, Right: &TreeNode{Val: 8}}, Right: &TreeNode{Val: 6, Left: &TreeNode{Val: 9}, Right: &TreeNode{Val: 10}}}
fmt.Println(ifIntersection(root1, root2)) //false
fmt.Println(GetIntersectionTreeRootWithRecursionII(root1, root2)) //false
fmt.Println("---------------结束---------------")
//fmt.Println(solution(root1, root2)) //false
//一个树不是另一个树的子树并且相交于叶节点
node := &TreeNode{Val: 5}
root1, root2 = &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}, Right: node}, Right: &TreeNode{Val: 3}}, &TreeNode{Val: 6, Left: node, Right: &TreeNode{Val: 7}}
fmt.Println("---------------一个树不是另一个树的子树并且相交于叶节点:---------------")
fmt.Println(ifIntersection(root1, root2))
fmt.Println(GetIntersectionTreeRootWithRecursionII(root1, root2))
fmt.Println("---------------结束---------------")

//fmt.Println(solution(root1, root2))
//一个树不是另一个树的子树并且相交于非叶子节点
node = &TreeNode{Val: 3, Left: &TreeNode{Val: 6}, Right: &TreeNode{Val: 7}}
root1, root2 = &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}, Right: &TreeNode{Val: 5}}, Right: node}, &TreeNode{Val: 8, Left: node, Right: &TreeNode{Val: 9}}
fmt.Println("---------------一个树不是另一个树的子树并且相交于非叶子节点:---------------")
fmt.Println(ifIntersection(root1, root2))
fmt.Println(GetIntersectionTreeRootWithRecursionII(root1, root2))
fmt.Println("---------------结束---------------")

//fmt.Println(solution(root1, root2))
//一个树是另一个树的子树
node = &TreeNode{Val: 3, Left: &TreeNode{Val: 6}, Right: &TreeNode{Val: 7}}
root1, root2 = &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}, Right: &TreeNode{Val: 5}}, Right: node}, node
fmt.Println("---------------一个树是另一个树的子树:---------------")
fmt.Println(ifIntersection(root1, root2))
fmt.Println(GetIntersectionTreeRootWithRecursionII(root1, root2))
fmt.Println("---------------结束---------------")

//fmt.Println(solution(root1, root2))
}

//判断两个树是否相交
//判断两个树是否相交
//采用Morris先序遍历可以在时间复杂度不变的情况下将空间复杂度将为O(1)
func ifIntersection(root1, root2 *TreeNode) bool {
//有一个为空,说明不相交
if root1 == nil || root2 == nil {
return false
}

//Morris先序遍历树1:第一个树的叶子节点的左指针指向第一个树根
var prev *TreeNode
cur := root1
for cur != nil {
if cur.Left == nil && cur.Right == nil {
cur.Left, cur = root1, cur.Right
} else if cur.Left == root1 {
cur = cur.Right
} else {
prev = cur.Left
for (prev.Right != nil) && (prev.Right != cur) { //找到左子树的最右节点
prev = prev.Right
}
//如果最右节点的左子树为空,则指向root1
if prev.Left == nil {
prev.Left = root1
}

if prev.Right == nil { //找到了最右节点
prev.Right = cur
cur = cur.Left
} else { //此时就是最右节点,只不过此时最右节点的右指针指向的不是nil,所以要置nil
prev.Right = nil
cur = cur.Right
}
}
}
//Morris先序遍历树2:如果遍历的时候发现左指针指向第1个树根,说明相交
cur, prev = root2, nil
var ret bool
for cur != nil {
if cur.Left == root1 {
ret, cur.Left = true, nil
} else if cur.Left == nil {
//如果当前节点是叶子节点
if cur.Right == nil {
cur.Left = nil
}
cur = cur.Right
} else {
prev = cur.Left
for (prev.Right != nil) && (prev.Right != cur) { //找到左子树的最右节点
prev = prev.Right
}
if prev.Left == root1 {
prev.Left = nil
ret = true
}

if prev.Right == nil { //找到了最右节点
//判断是否为叶子节点
if prev.Left == root1 {
prev.Left = nil
ret = true
}
prev.Right = cur
cur = cur.Left
} else { //此时就是最右节点,只不过此时最右节点的右指针指向的不是nil,所以要置nil
prev.Right = nil
cur = cur.Right
}
}
}

return ret
}

评论