剑指offer 57.二叉树的下一个结点

剑指offer 57.二叉树的下一个结点

题目

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

思路

这里的next命名有点憨，指向父节点的命名为next。

1. 中序是左中右，如果结点存在右子树，那么就找到右子树的最左节点，
2. 如果不存在右子树
   1. 若该点为父节点的左子节点，那么下一个就是父节点。
   2. 若该点为父节点的右子节点，那么递归向上，直到找到结点为父节点的左子节点为止。

代码

public class TreeLinkNode {

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

  TreeLinkNode(int val) {
    this.val = val;
  }
}

public TreeLinkNode GetNext(TreeLinkNode pNode) {
  if (pNode == null) {
    return null;
  }
  if (pNode.right != null) {
    pNode = pNode.right;
    while (pNode.left != null) {
      pNode = pNode.left;
    }
    return pNode;
  }
  while (pNode.next != null) {
    if (pNode.next.left == pNode) {
      return pNode.next;
    }
    pNode = pNode.next;
  }
  return null;
}