二叉树的下一个节点

发表于 | 分类于

题目

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

思路

绘图分析，状态考虑全面即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function GetNext(pNode) {
  if (pNode === null) {
    return null;
  }
  if (pNode.right !== null) {
    // 第1种
    pNode = pNode.right;
    while (pNode.left !== null) {
      pNode = pNode.left;
    }
    return pNode;
  }
  while (pNode.next !== null) {
    // 第2种
    if (pNode === pNode.next.left) {
      return pNode.next;
    }
    pNode = pNode.next;
  }
  return null;
}