给定一个二叉树和其中的一个节点,如何找出中序遍历序列的下一个节点?。注意,树中的节点不仅包含左右子节点,同时包含指向父节点的指针。
节点代码如下:
/**
* 二叉树节点
* @Author rex
* 2018/6/13
*/
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
// 父节点
TreeLinkNode parent = null;
TreeLinkNode(int val) {
this.val = val;
}
}
- 普通二叉树(完全二叉树;不完全二叉树)。
- 特殊二叉树(所有的节点都没有右子节点的二叉树;所有节点都没有左子节点的二叉树;只有一个节点的二叉树;二叉树的根节点指针为null)。
- 不同位置的节点的下一个节点(下一个节点为当前节点的右子节点、右字数的最左子节点、父节点、跨层的父节点等;当前节点没有下一个节点)
- 考察应聘者对二叉树中序遍历的理解程度。
- 考察应聘者分析复杂问题的能力。应聘者只有画出二叉树的结构图、通过具体的例子找出中序遍历下一个节点的规律,才有可能设计出可行的算法。(感觉上找规律很重要)
通过对下一个节点的情况分析,主要有以下两种情况:
没有进行详细的分析,没有找规律,没有做出来!!!!!!
/**
* 二叉树的下一个节点
*
* @Author rex
* 2018/6/13
*/
public class Solution {
/**
* 寻找二叉树的下一个节点
*
* @param pNode
* @return
*/
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode == null) {
return null;
}
// 第一种情况
if (pNode.right != null) {
TreeLinkNode rNode = pNode.right;
while (rNode.left != null) {
rNode = rNode.left;
}
return rNode;
} else {
// 第二种情况
while (pNode.parent != null) {
TreeLinkNode parentNode = pNode.parent;
if (parentNode.left == pNode) {
return parentNode;
}
pNode = pNode.parent;
}
}
return null;
}
}