Java实现二叉树中序遍历的下一个节点

x33g5p2x  于2021-03-13 发布在 Java  
字(1.1k)|赞(0)|评价(0)|浏览(219)

给定一个二叉树和其中的一个节点,如何找出中序遍历序列的下一个节点?树中的节点除了左右子节点外,还包含父节点。

规则
输入:TreeNode node
输出:下一个节点TreeNode node
case:

节点为null
获得中序遍历的下一个节点 节点有两个要考虑的因素:
1.node是其父节点的左节点还是右节点
2.node是否有左右节点,
左/右	无左无右	有左无右	无左有右	有左有右
左	左1	左2	左3	左4
右	右1	右2	右3	右4

思路
对上面的几种情况进行统计,
左-无左无右:父节点
左-有左无右:父节点
左-无左有右:右子树的最左节点
左-有左有右:右子树的最左节点

右-无左无右:沿着父节点一直往上找,直到找到一个节点是其父的左节点
右-有左无右:沿着父节点一直往上找,直到找到一个节点是其父的左节点
右-无左有右:右子树的最左节点
右-有左有右:右子树的最左节点

综合上面的情况,如果节点node有右节点,则查找右子树的最左边的节点;如果没有右节点,那么综合一下可以总结为,从node出发,向上查找,直到找到一个节点是其父的左节点 ,由于node位于左节点时,会立即找到,因此返回的是父节点。

代码

public TreeNode getNext(TreeNode node) {
	if(node == null) {
		return null;
	}
	if(node.right != null) { // node有右子树
		return getLeft(node.right);
	}else { // node右子树为null
		if(node.parent == null) {
			return null;
		}
		/**********************************************
        if(node == node.parent.left) { // 左节点
			return node.parent;
		}else if(node == node.parent.right) { // 右节点
			TreeNode tmp = node.parent;
			while(tmp.parent != null && tmp.parent.right == tmp) {
				tmp = tmp.parent;
			}
			return tmp.parent;
		}***************************************************/
		TreeNode tmp = node;
		while(tmp.parent != null && tmp.parent.right == tmp) {
			tmp = tmp.parent;
		}
		return tmp.parent;
	}
}

private TreeNode getLeft(TreeNode tree) {
	if(tree.left == null)
		return tree;
	return getLeft(tree.left);
}

相关文章

热门文章

更多