剑指OfferJZ57：二叉树的下一个节点-java版

ゞ浴缸里的玫瑰 2022-10-15 13:56 148阅读 0赞

### 剑指OfferJZ57：二叉树的下一个节点-java版 ###

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

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

中序遍历：左中右  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]

寻找当前节点（pNode）的下一个节点,主要分三种情况：

**第一种情况**，当前节点右孩子不为空  
如：节点2 它的下一个节点是它的右孩子6 （右孩子下没有孩子）  
如：节点3 它的下一个节点是它的右孩子8 （右孩子下没有孩子）  
如：节点1 它的下一个节点是它的右孩子3，但右孩子下也有孩子，那么最终节点1的下一个节点就取其右孩子的左孩子7

**第二种情况**，当前节点右孩子为空，并且当前节点是父亲节点的左孩子  
如：节点5 它的下一个节点是它的父节点2  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]

**第三种情况**，当前节点右孩子为空，并且当前节点是父亲节点的右孩子  
如：节点6 它的下一个节点是它的父节点的父节点1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]

注意：当当前节点为最后一个节点时，它的下一个节点为空，题中需要对这种情况进行判断

public class Solution { 
        public TreeLinkNode GetNext(TreeLinkNode pNode) { 
            //pNode当前节点
            if(pNode.right!=null){ 
                //第一种情况，pNode节点的右孩子不为空
                pNode=pNode.right;
                while(pNode.left!=null){ //pNode节点的右孩子的左孩子也不为空时
                    pNode=pNode.left;
                }
                return pNode;
            }else{ 
                //tempNode当前节点的父亲结点
                TreeLinkNode tempNode=pNode.next;
                if(tempNode==null){ //当前节点为根节点（根节点的父节点tempNode为null）
                    return null;
                }
                if(tempNode.left==pNode){ 
                    //第二种情况，当前节点右孩子为空，并且当前节点是父亲节点的左孩子，那么当前节点pNode的下一个节点是它的父节点
                    return tempNode;
                }else{ 
                    //第三种情况，当前节点右孩子为空，并且当前节点是父亲节点的右孩子,那么当前节点pNode的下一个节点是它的父节点的父节点
                    //flag=false标记当前节点为最后一个节点（最后一个节点的下一个节点为null）
                    boolean flag=false;
                    while(tempNode.next!=null){ 
                        if(tempNode.next.left==tempNode){ 
                            flag=true;//当前节点非最后一个节点
                            break;
                        }
                        tempNode=tempNode.next;
                    }
                    //flag为true时，说明pNode所指的节点不是二叉树中最后一个节点
                    //tempNode.next当前节点父节点的父节点
                    return flag ? tempNode.next: null;
                }
            }
    
        }
    }
    class TreeLinkNode{ 
        int val;
        TreeLinkNode left=null;
        TreeLinkNode right=null;
        TreeLinkNode next=null;
    
        TreeLinkNode (int val){ 
            this.val=val;
        }
    }

![在这里插入图片描述][20210526113052179.gif_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20221014/103f6dfdbc074c55b1f30845a88e8e62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]: /images/20221014/0d1de8f191c24125ae8afe9b808de52e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]: /images/20221014/bc52bf1b3dbb4695b5b0cafa10cd8a83.png
[20210526113052179.gif_pic_center]: /images/20221014/cb966b794cac4a3f85139c18d4dd431a.png