本文共 894 字,大约阅读时间需要 2 分钟。
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
若当前结点有右子树,中序遍历下一结点为右子树的最左结点。若当前结点无右子树,且是其父结点的左子树,则中序遍历下一结点为其父结点。若当前结点无右子树,且是其父结点的右子树,则验证其父结点的中序遍历下一结点。时间复杂度O(n),空间复杂度O(1)。
/*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; }}
向上验证父结点无需递归,while循环即可。
转载地址:http://kfuki.baihongyu.com/