# 题目链接
# 题目描述
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回 。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
# 解题思路
package main
/*
type TreeLinkNode struct {
Val int
Left *TreeLinkNode
Right *TreeLinkNode
Next *TreeLinkNode
}
*/
func GetNext(pNode *TreeLinkNode) *TreeLinkNode {
p:=pNode
if p.Right!=nil{
p=p.Right
for{
if p.Left!=nil{
p=p.Left
}else{
return p
}
}
}else{
for p.Next!=nil&&p.Next.Right ==p{
p=p.Next
}
return p.Next
}
}
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
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