题目

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

思路

中序遍历的顺序 左 - 根 - 右

所以寻找下一个节点的优先级应该反过来 优先级 右 - 根 - 左

• 右节点不为空 - 取右节点的最左侧节点
• 右节点为空 - 如果节点是父亲节的左节点 取父节点
• 右节点为空 - 如果节点是父亲节的右节点 父节点已经被遍历过，再往上层寻找...
• 左节点一定在当前节点之前被遍历过

以下图的二叉树来分析：

中序遍历： CBDAEF

• B - 右节点不为空，下一个节点为右节点D
• C - 右节点为空，C是父节点的左节点，取父节点B
• D - 右节点为空，D是父节点的右节点，再往上蹭分析，B是其父节点的左节点，取B的父节点A
• F - 右节点为空，F是父节点的右节点，没有符合条件的节点，F为遍历的最后一个节点，返回null

代码

    /*function TreeLinkNode(x){
        this.val = x;
        this.left = null;
        this.right = null;
        this.next = null;
    }*/
    function GetNext(pNode) {
      if (!pNode) {
        return null;
      }
      if (pNode.right) {
        pNode = pNode.right;
        while (pNode.left) {
          pNode = pNode.left;
        }
        return pNode;
      } else {
        while (pNode) {
          if (!pNode.next) {
            return null;
          } else if (pNode == pNode.next.left) {
            return pNode.next;
          }
          pNode = pNode.next;
        }
        return pNode;
      }
    }

考察点

• 二叉树
• 复杂问题拆解