剑指Offer 8. 二叉树的下一个节点
题目
给定一棵二叉树和其中的一个结点,如何找出中序遍历顺序的下一个结点?树中的结点除了有两个分别指向左右子结点的指针以外,还有一个指向父结点的指针。
解答1[Java]:
主要分为两种情况:
①如果一个节点的右子树不为空,那么在中序遍历的下一个节点就是其【右子树的最左节点】。
②如果一个节点的右子树为空,那么在中序遍历的下一个节点就是其【最近的一个祖先节点,这个祖先节点的左子树包含该节点】。
1 | public class Solution { |
给定一棵二叉树和其中的一个结点,如何找出中序遍历顺序的下一个结点?树中的结点除了有两个分别指向左右子结点的指针以外,还有一个指向父结点的指针。
主要分为两种情况:
①如果一个节点的右子树不为空,那么在中序遍历的下一个节点就是其【右子树的最左节点】。
②如果一个节点的右子树为空,那么在中序遍历的下一个节点就是其【最近的一个祖先节点,这个祖先节点的左子树包含该节点】。
1 | public class Solution { |