首先我们先了解一下二叉树的三种遍历方法:

  • 前序遍历:从根节点开始,根在前,从左往右,一棵树的根永远在左子树前面,左子树又永远在右子树前面;
  • 中序遍历:从最左节点开始,根在中,从左往右,一棵树的左子树永远在根前面,根永远在右子树前面;
  • 后序遍历:也是从最左节点开始,根在后,从左往右,一棵树的左子树永远在右子树前面,右子树永远在根前面。

比如下面一张图

image
image
  • 前序遍历为:ABDGHECKFIJ
  • 中序遍历为:GDHBEAKCIJF
  • 后序遍历为:GHDEBKJIFCA

了解了二叉树的大致遍历方式,我们来看下题目:

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

通过中序遍历我们可以知道一个节点的下一个节点有两种情况:

  • 如果一个节点的右子树不为空,那么该节点的下一个节点是右子树的最左节点,比如上图中C的后一个节点是I;
  • 如果一个节点的右子树为空,那么向上找第一个左链接指向的树包含该节点的父节点。比如上图H的下一个节点是B。

接下来看代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 定义一棵树

public class TreeLinkNode {

int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;

TreeLinkNode(int val) {
this.val = val;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
//判断该节点是否存在右子节点
if(pNode.right != null){
//如果有右子树,则找右子树的最左节点
TreeLinkNode rightNode = pNode.right;
while(rightNode.left != null)
rightNode = rightNode.left;
return rightNode;
}else{
//没右子树,则找第一个当前节点是父节点左孩子的节点
while(pNode.next != null){
TreeLinkNode parentNode = pNode.next;
if(parentNode.left == pNode)
return parentNode;
pNode = pNode.next;
}
}
return null;
}
}