https://www.nowcoder.com/profile/163334/codeBookDetail?submissionId=1512899中weizier的回答

题目描述

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

思路

中序遍历是左根右的顺序 如果有右子树，则找右子树的最左节点 如果没右子树，则找第一个当前节点是父节点的左节点，并返回找到结点的父结点 中序遍历：ACBDFHEMG 举例： 对于A，没有右子树，A是父节点C的左节点，返回找到结点A的父结点C。 对于C，有右子树，B是右子树的最左节点，返回B。 对于D，没有右子树，D不是父节点C的左节点， 向上找（父结点找），C是父节点F的左节点，返回找到结点C的父结点F。

java实现

/* public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } } */ public class Solution { public TreeLinkNode GetNext(TreeLinkNode node) { if(node==null) return null; if(node.right!=null){ //如果有右子树，则找右子树的最左节点 node = node.right; while(node.left!=null) node = node.left; return node; } while(node.next!=null){ //没右子树，则找第一个当前节点是父节点左孩子的节点，并返回找到结点的父结点 if(node.next.left==node) return node.next; node = node.next; } return null; //退到了根节点仍没找到，则返回null } }