# 题目

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

# 思路

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

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

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

以下图的二叉树来分析:

foo

中序遍历: 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;
      }
    }

# 考察点

  • 二叉树
  • 复杂问题拆解