【剑指offer】面试题8：二叉树的下一个节点

旧城等待， 2022-04-01 15:18 141阅读 0赞

> **题目：给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。**

我们来分析下，求给定节点的下一个节点的的几种情况：

1、若二叉树为空，则返回空；

2、给定节点的右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子节点的指针找到的叶子节点即为下一个节点（即给定节点的右子树中的最左子节点）；

3、给定节点不是根节点（即节点的父节点不为空）。如果该节点是其父节点的左孩子，则直接返回它的父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，直到找到一个是它父节点的左子节点的节点，那么它的父节点即是给定节点的下一个节点，返回结果。

public class SearchNextNode {
    
    	public static BinaryTreeNode getNextNode(BinaryTreeNode node) {
    
    		if (node == null) {
    			return null;
    		}
    
    		// 如果当前节点有右子树，则找到右子树中的最左节点即为当前节点的下一个节点
    		if (node.rightNode != null) {
    			node = node.rightNode;
    			while (node.leftNode != null) {
    				node = node.leftNode;
    			}
    			return node;
    		}
    
    		// 如果当前节点没有右子树，则找第一个当前节点是父节点左孩子的节点
    		// 那么下一个节点就是这个当前节点的父节点
    		while(node.parent != null){
    			if(node.parent.leftNode == node) {
    				return node.parent;
    			}
    			node = node.parent;
    		}
    
    		// 如果退到了根节点也没有找到，则返回null
    		return null;
    	}
    
    	public class BinaryTreeNode {
    
    		public int value; // 当前节点的值
    		public BinaryTreeNode leftNode; // 当前节点的左子节点
    		public BinaryTreeNode rightNode; // 当前节点的右子节点
    		public BinaryTreeNode parent; // 当前节点的父节点
    
    		public BinaryTreeNode() {
    
    		}
    
    		public BinaryTreeNode(int value) {
    			this.value = value;
    			this.leftNode = null; // 刚创建时，左右子树都为空
    			this.rightNode = null;
    			this.parent = null;
    		}
    	}
    
    	/**
    	 * 测试
    	 */
    	public static void main(String[] args) {
    
    		SearchNextNode node = new SearchNextNode();
    
    		BinaryTreeNode root = node.new BinaryTreeNode(1);
    		BinaryTreeNode node1 = node.new BinaryTreeNode(2);
    		BinaryTreeNode node2 = node.new BinaryTreeNode(3);
    		BinaryTreeNode node3 = node.new BinaryTreeNode(4);
    		BinaryTreeNode node4 = node.new BinaryTreeNode(5);
    		BinaryTreeNode node5 = node.new BinaryTreeNode(6);
    		BinaryTreeNode node6 = node.new BinaryTreeNode(7);
    		BinaryTreeNode node7 = node.new BinaryTreeNode(8);
    		BinaryTreeNode node8 = node.new BinaryTreeNode(9);
    
    		root.leftNode = node1;
    		root.rightNode = node2;
    		root.parent = null;
    		node2.parent = root;
    		node1.parent = root;
    		node1.leftNode = node3;
    		node3.parent = node1;
    		node1.rightNode = node4;
    		node4.parent = node1;
    
    		node2.leftNode = node5;
    		node5.parent = node2;
    		node2.rightNode = node6;
    		node6.parent = node2;
    		node3.rightNode = node7;
    		node7.parent = node3;
    
    		node4.rightNode = node8;
    		node8.parent = node4;
    		
    		BinaryTreeNode N1 = getNextNode(node8);   // 1
    		System.out.println(N1.value);
    		BinaryTreeNode N2 = getNextNode(node4);   // 9
    		System.out.println(N2.value);
    		BinaryTreeNode N3 = getNextNode(node7);   // 2
    		System.out.println(N3.value);
    		BinaryTreeNode N4 = getNextNode(node6);   // null
    		System.out.println(N4);
    	}
    }