剑指offer_二叉树的下一个节点

桃扇骨 2022-06-09 02:14 139阅读 0赞

/*
    给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
    注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
    
    思路：
    根据给出结点找到根节点，再进行中序遍历，中序遍历过程添加next指针
    本地运行正确，但是在牛客网上运行出错，为什么？
    
    与面试题27将二叉搜索树转换为排序的双向链表类似，中序遍历的过程添加指针变成双向链表
    
    */
    
    class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
    	TreeLinkNode next = null;
    	TreeLinkNode parent = null;
    
        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    
    class  GetNext
    {
    	static TreeLinkNode pNext=null;
    	public static TreeLinkNode getNext(TreeLinkNode pNode)
        {
    		//找到根节点
    		TreeLinkNode pTemp=pNode;
            while (pTemp.parent!=null)
            {
    			pTemp=pTemp.parent;
            }
    		
    		//中序遍历并添加next指针
    		traversal(pTemp);
    		
    		//找到中序第一个节点
    		while(pTemp.left!=null)
    			pTemp=pTemp.left;
    
    		//从第一个节点开始，按照next指针找到指定节点的下一个节点
    		while (pTemp.next!=null)
    		{
    			if (pTemp==pNode)
    			{
    				return pTemp.next;
    			}else
    				pTemp=pTemp.next;
    		}
    
    		return null;
        }
    
    	public static void traversal(TreeLinkNode pHead)
        {
    		if (pHead.left!=null)
    		{
    			traversal(pHead.left);
    		}
    		if (pNext!=null)
    		{
    			pNext.next=pHead;
    		}
    
    		pNext=pHead;
    		if (pHead.right!=null)
    		{
    			traversal(pHead.right);
    		}
        }
    
    	/*
    	剑指offer思路：
    	1、有右子树的，那么下个结点就是右子树最左边的点；
    	2、没有右子树的，也可以分成两类，
    	a)是父节点左孩子 ，那么父节点就是下一个节点；
    	b)是父节点的右孩子，找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置，
    		如果找到这样的结点，当前结点的父节点就是下一个结点，如果没有找到，当前结点就是尾节点。
    	*/
    
    	public static TreeLinkNode getNext2(TreeLinkNode pNode)
        {
    		if (pNode==null)
    		{
    			return null;
    		}
    
    		//有右子树的，那么下个结点就是右子树最左边的点；
    		if (pNode.right!=null)
    		{
    			TreeLinkNode pTemp=pNode.right;
    			while (pTemp.left!=null)
    			{
    				pTemp=pTemp.left;
    			}
    			return pTemp;
    		}
    
    		//没有右子树
    		while (pNode.parent!=null)
    		{
    			if (pNode.parent.left==pNode)//是父节点左孩子 ，那么父节点就是下一个节点；
    			{
    				return pNode.parent;
    			}else	//是父节点的右孩子
    			{
    				pNode=pNode.parent;
    			}	
    		}
    
    		return pNode.parent;
    	}
    
    	public static void main(String[] args) 
    	{
    		TreeLinkNode node1=new TreeLinkNode(1);
    		TreeLinkNode node2=new TreeLinkNode(2);
    		TreeLinkNode node3=new TreeLinkNode(3);
    		TreeLinkNode node4=new TreeLinkNode(4);
    		TreeLinkNode node5=new TreeLinkNode(5);
    		TreeLinkNode node6=new TreeLinkNode(6);
    		TreeLinkNode node7=new TreeLinkNode(7);
    
    		node1.left=node2;
    		node1.right=node3;
    		node2.left=node4;
    		node2.right=node5;
    		node3.left=node6;
    		node3.right=node7;
    
    		node4.parent=node2;
    		node5.parent=node2;
    		node6.parent=node3;
    		node7.parent=node3;
    		node2.parent=node1;
    		node3.parent=node1;
    
    		System.out.println(getNext(node5).val);
    	}
    }