08. 二叉树的下一个节点

来源

https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e

题目

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

示例:

例如，二叉树：

       8
     /   \
    6     10
  /  \   /  \
 5   7  9   11

给 5 返回 6，给 6 返回 7，给 7 返回 8，给 8 返回 9

限制：

0 <= 节点个数 <= 5000

思路

如果节点有右子节点，找出右子树最左侧的节点；
如果没有右子节点，如果此节点是父节点的右节点，则一直向上查找，直到当前节点不是父节点的右节点时，返回当前节点的父节点。

解题

/**
 * function TreeLinkNode(x){
 *     this.val = x;
 *     this.left = null;
 *     this.right = null;
 *     this.next = null; // 题目中的next实际上是parent
 * }
 */
function GetNext(pNode) {
  if (!pNode) return null;
  if (pNode.right) {
    let cur = pNode.right;
    while (cur.left) {
      cur = cur.left;
    }
    return cur;
  }
  if (pNode.next) {
    let cur = pNode;
    let curParent = pNode.next;
    while (curParent && cur === curParent.right) {
      cur = curParent;
      curParent = curParent.next;
    }
    return curParent;
  }
  return null;
}

从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch