二叉树的下一个结点&二叉树的上一个结点

二叉树的下一个结点

题目：给定一棵二叉树和其中一个结点，如何找出中序遍历的下一个结点，树中的结点除了有两个分别指向左右子结点的指针外，还有一个指向父节点的指针

 最笨的方法就是一直网上回溯，直到找到了头结点，然后从头结点开始重新中序遍历一次树，然后得到答案  还有一种比较巧妙的方法，先判断当前结点有没有右子树，如果有，直接打印右子树中最左的结点即为答案；如果没有，就往上回溯，假设当前结点是x，父节点是p，如果x是p的左孩子，p就是答案，如果不是，就一直向上回溯x = p;p = p.parent;

二叉树的上一个结点

题目：给定一棵二叉树和其中一个结点，如何找出中序遍历的上一个结点，树中的结点除了有两个分别指向左右子结点的指针外，还有一个指向父结点的指针

 这个的做法正好与上面相反，先判断当前结点x是否有左子树，如果有，打印左子树最右的结点；如果没有，还是网上回溯，如果x是p的右孩子，p就是答案