【题8 二叉树的下一个节点】Java实现

喜欢ヅ旅行 2022-03-29 02:58 208阅读 0赞

**【面试题8 二叉树的下一个节点】**  
**【题目】**  
给定 一个二叉树和其中的一个节点，如何找出中序遍历的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。  
**例如**：二叉树中序遍历\{d，b，h，e，i，a，f，c，g\}  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
实线：父节点->子节点  
虚线：子节点->父节点  
**分析：**  
**情况1：**  
如果一个节点**有右子树**，那么它的下一个节点就是它的右子树中的最左子节点。  
即从右子节点出发一直沿着指向左子节点的指针，找到它下一个节点。  
**即b的下一个节点为h**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
**a的下一个节点为f**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]  
**情况2：**  
**没有右子树：**  
如果**节点是它父亲的左子节点**，下一节点是它的父节点，  
**即d的下一个节点为b，**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 3]  
**f的下一个节点为c**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 4]  
**情况3：**  
既没有右子树，并且还**是它父节点的右子节点**  
沿着父节点的指针一直向上遍历，直到找到一个是它的父节点的左节点的节点，如果这样的节点存在，那么这个节点的父节点就是我们要找的下一个节点。  
**即i沿着父节点指针向上遍历到e，e是它的父节点b的右节点，继续向上到b，b是父节点a的左子节点，即i的下一个节点是b的父节点a**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 5]  
**实现**

package ti8;
    
    public class SearchNextNode {
    	public class BinaryTreeNode{
    		int val;
    		BinaryTreeNode left;
    		BinaryTreeNode right;
    		BinaryTreeNode parent;
    		public BinaryTreeNode(int val){
    			this.val = val;
    			this.left = left;
    			this.right = right;
    			this.parent = parent;
    		}
    	}
    	public static BinaryTreeNode nextNode(BinaryTreeNode node){
    		BinaryTreeNode nextnode = null;
    		if(node == null)return null;
    		//情况1：如果该结点右子树不为空，那么他的下一个节点就是他的右子树中的最左节点，
    		//即从右子节点出发，一直沿着指向左子节点的指针，找到他的下一个节点
    		if(node.right != null){
    			nextnode = node.right;
    			while(nextnode.left != null){
    				nextnode = nextnode.left;
    			}
    		}
    		
    		//情况2：如果该节点右子树为空，如果节点是他的父节点的左子节点，
    		//下一个节点是他的父节点
    		if(node.right == null){
    			if(node.parent != null){
    				//如果该节点是父节点的左子树
    				if(node.parent.left == node){
    					System.out.println("该节点是父节点的左子树");
    					nextnode = node.parent; 
    				}
    				//情况3：如果该节点是父节点的右子树，
    				//沿着指向父节点的指针一直向上遍历，直到找到一个是它的父节点的左子节点的节点
    				//如果这样的节点存在，那么这个节点的父节点就是我们要找到下一个节点
    				else if(node.parent.right == node){
    					while(node.parent != null && node.parent.right == node){
    						System.out.println("该节点是父节点的右子树"+node.val);
    						node = node.parent;
    					}
    					nextnode = node.parent;
    				}
    			}
    		}
    		return nextnode;
    	}
    	public static void main(String[] args) {
    		SearchNextNode sn = new SearchNextNode();
    		//创建一棵树
    		/**
    		 *             1
    		 *     2                 3
    		 *  4      5         6       7
    		 *    8      9  
    		 */
    		BinaryTreeNode root  = sn.new BinaryTreeNode(1);
    		BinaryTreeNode node1 = sn.new BinaryTreeNode(2);
    		BinaryTreeNode node2 = sn.new BinaryTreeNode(3);
    		BinaryTreeNode node3 = sn.new BinaryTreeNode(4);
    		BinaryTreeNode node4 = sn.new BinaryTreeNode(5);
    		BinaryTreeNode node5 = sn.new BinaryTreeNode(6);
    		BinaryTreeNode node6 = sn.new BinaryTreeNode(7);
    		BinaryTreeNode node7 = sn.new BinaryTreeNode(8);
    		BinaryTreeNode node8 = sn.new BinaryTreeNode(9);
    		root.left = node1;
    		root.right = node2;
    		root.parent = null;
    		node2.parent = root;
    		node1.parent = root;
    		node1.left = node3;
    		node3.parent = node1;
    		node1.right = node4;
    		node4.parent = node1;
    		
    		node2.left = node5;
    		node5.parent = node2;
    		node2.right = node6;
    		node6.parent = node2;
    		node3.right = node7;
    		node7.parent = node3;
    		
    		node4.right = node8;
    		node8.parent = node4;
    		BinaryTreeNode N1 = nextNode(node8);
    		System.out.println(N1.val);
    		BinaryTreeNode N2 = nextNode(node4);
    		System.out.println(N2.val);
    		BinaryTreeNode N3 = nextNode(node7);
    		System.out.println(N3.val);
    		BinaryTreeNode N4 = nextNode(node6);
    		//System.out.println(N4.val);
    		
    	}
    
    }

参考：  
1.《剑指offer》  
2.[https://blog.csdn.net/sytloveyxj/article/details/78934916][https_blog.csdn.net_sytloveyxj_article_details_78934916]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220329/e9ea2723165d464aad45b1fb798017b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220329/46146afb95344ffa8017d534b1012370.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]: /images/20220329/ca42cf3ffcbd4b4aa0821dcbb92ced06.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 3]: /images/20220329/7647d799a86d49ce938e8472daa43c1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 4]: /images/20220329/925ee69148054aa193077c877ab42ed8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 5]: /images/20220329/6791c0cbba9c4e16b4b1f63739f959a2.png
[https_blog.csdn.net_sytloveyxj_article_details_78934916]: https://blog.csdn.net/sytloveyxj/article/details/78934916