[剑指OFFER]之树：JZ8 二叉树的下一个结点

文章目录

1.题目

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

2.解法

2.1 树的结构

publicclassTreeLinkNode{int val;TreeLinkNode left =null;TreeLinkNode right =null;TreeLinkNode next =null;TreeLinkNode(int val){this.val = val;}}

要求实现的方法

publicclassSolution{publicTreeLinkNodeGetNext(TreeLinkNode pNode){}}

2.2 解法1

定义一个中序遍历的方法，在遍历时把顺序记录到

List<TreeLinkNode> intravels

中，在

GetNext

方法内，通过下标关系来获取下一个。

缺点，浪费空间O(n)。

publicvoidintravel(TreeLinkNode node,List<TreeLinkNode> intravels){if(node==null)return;intravel(node.left,intravels);
        intravels.add(node);intravel(node.right,intravels);}publicTreeLinkNodeGetNext(TreeLinkNode pNode){List<TreeLinkNode> intravels =newLinkedList<>();TreeLinkNode root = pNode;while(root.next!=null){
            root = root.next;}intravel(root,intravels);int pos = intravels.indexOf(pNode);if(pos==-1||pos==intravels.size()-1)returnnull;TreeLinkNode nextNode = intravels.get(pos+1);return nextNode;}

2.3 解法2

分情况讨论。

中序遍历的特点是，要先左子树，然后是根，然后右子树。

一、如果该节点有右子树，那么接下来，就是访问右子树咯。对于右子树而言，会持续递归找到其最左叶子，这个节点就是next元素了。

二、如果该节点没有右子树，这时，就又分两种情况

A、pNode对于父节点而言，是父节点的左子树，此时返回父节点。

B、pNode对于父节点而言，是父节点的右子树。这就比较麻烦。要持续找到祖先，且祖先是一个左孩子，返回祖先的父节点。

publicTreeLinkNodeGetNext(TreeLinkNode pNode){//如果该节点有右子树,最左子树的叶子if(pNode.right !=null){TreeLinkNode target = pNode.right;while(target.left !=null){
                target = target.left;}return target;}//如果该节点没有右子树//那么分为两种情况，if(pNode.next !=null){//1，自己是父节点的左子树,返回父节点if(pNode.next.left == pNode)return pNode.next;//2.自己是父节点的右子树，则先找父节点，然后看父节点是左派还是右派。TreeLinkNode parent = pNode.next;//找到不是右子树的祖先while(parent.next !=null){if(parent == parent.next.right)
                    parent = parent.next;elsebreak;}//终于找到祖先不是右子树了。//返回祖先的父亲return parent.next;}returnnull;}

总结

如果要节约空间，就要对pNode的位置进行讨论分类。三类情况，最后一种最复杂。

算法系列在github上有一个开源项目，主要是本系列博客的demo代码。https://github.com/forestnlp/alg
如果您对软件开发、机器学习、深度学习有兴趣请关注本博客，将持续推出Java、软件架构、深度学习相关专栏。
您的支持是对我最大的鼓励。