一、题目
————————————————
给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？ 树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。
————————————————
二、思路
————————————————
首先自己在草稿纸上画图，进行分析（不再展开）。可以发现下一个结点的规律为：
1.若当前结点有右子树时，其下一个结点为右子树中最左子结点；
2.若当前结点无右子树时，
（1）若当前结点为其父结点的左子结点时，其下一个结点为其父结点；
（2）若当前结点为其父结点的右子结点时，继续向上遍历父结点的父结点，直到找到一个结点是其父结点的左子结点（与（1）中判断相同），该结点即为下一结点。
————————————————
中序遍历，下一个结点有两种情况
a. 当前结点有右子树，就找出右子树中的最左的结点；
b. 当前结点没有右子树 就往它的父节点找，找到第一个结点是它的父节点的左子节点的结点时停止，下一个结点就是该节点的父节点；
作如下表述：
（1）：有右子树的，那么下个结点就是右子树最左边的点；
（2）：没有右子树的，给出结点是父结点的左孩子，返回父结点；
（3）：没有右子树，给出结点是父结点的右孩子，把给出结点的父节点作为下一个遍历的节点，向上回溯，直到当前结点是其父节点的左孩子时停止【直到找到一个父节点X，并且这个父节点X是其本身的父节点Y的左孩子为止】，下一个结点就是当前结点的父节点proot【return proot】。【TreeLinkNode *proot=pNode->next；proot->left==pNode，pNode是当前节点，pNode->next是当前节点的父节点，proot->left是其父结点的左结点】，
例子： 先序遍历：1 2 4 6 7 5 8 3（根左右）； 中序遍历：6 4 7 2 5 8 1 3（左根右）【给出的结点为8，下一个结点为1为例】 后序遍历：6 7 4 8 5 2 3 1（左右根）
————————————————
三、解决问题
————————————————
测试用例
1.正常二叉树
2.左斜树、右斜树
4.单个结点
5.null
6.不同位置结点的下一结点（即上面分析的几种情况、无下一节点等情况）
————————————————
package swordoffer;
/**
* @author LQ
* @version 1.0
* @date 2020-03-13 14:24
*/
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
package swordoffer;
/**
* @author LQ
* @version 1.0
* @date 2020-03-13 14:23
*/
/**
* 题目：给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？
树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。
*/
public class Solution07 {
public static void main(String[] args) {
System.out.println("==============================");
Solution07 sword = new Solution07();
sword.test1();
System.out.println("==============================");
sword.test2();
System.out.println("==============================");
sword.test3();
System.out.println("==============================");
sword.test4();
System.out.println("==============================");
}
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if(null == pNode){
System.out.println("结点为null");
return null;
}
//1.若当前结点有右子树时，其下一个结点为右子树中最左子结点--对应图1
if(pNode.right != null){
TreeLinkNode node = pNode.right;
while(node.left != null){
node = node.left;
}
return node;
}else{
//2：没有右子树的，给出结点是父结点的左孩子，返回父结点--对应图2,3
while (pNode.next != null){
TreeLinkNode parent = pNode.next;
if(parent.left == pNode){
return parent;
}
pNode = pNode.next;
}
}
return null;
}
// ==================================测试代码==================================
//创建树较为繁琐，未包括所有测试代码。
public void test1() {
TreeLinkNode node = null;
TreeLinkNode nextNode = GetNext(node);
if(nextNode!=null)
System.out.println(nextNode.val);
else
System.out.println("无下一结点");
}
/**
* 1：有右子树的，那么下个结点就是右子树最左边的点
*/
public void test2() {
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);
node1.left = node2;
node1.right = node3;
node2.next = node1;
node3.next = node1;
node2.left = node4;
node2.right = node5;
node4.next = node2;
node5.next = node2;
node5.left = node6;
node6.next=node5;
TreeLinkNode nextNodeOf1=GetNext(node2);
if(nextNodeOf1!=null)
System.out.println("2结点的下一个结点值为："+nextNodeOf1.val);
else
System.out.println("2结点无下一结点");
}
/**
* 2：没有右子树的，给出结点是父结点的左孩子，返回父结点；
*/
public void test3() {
TreeLinkNode node1 = new TreeLinkNode(1);
TreeLinkNode node2 = new TreeLinkNode(2);
TreeLinkNode node3 = new TreeLinkNode(3);
TreeLinkNode node4 = new TreeLinkNode(4);
TreeLinkNode node6 = new TreeLinkNode(6);
TreeLinkNode node7 = new TreeLinkNode(7);
node1.left = node2;
node1.right = node3;
node2.next = node1;
node3.next = node1;
node2.left = node4;
node4.next = node2;
node4.left = node6;
node4.right = node7;
node6.next = node4;
node7.next = node4;
TreeLinkNode nextNodeOf1=GetNext(node2);
if(nextNodeOf1!=null)
System.out.println("2结点的下一个结点值为："+nextNodeOf1.val);
else
System.out.println("2结点无下一结点");
}
/**
* 3：没有右子树，给出结点是父结点的右孩子
* 把给出结点的父节点作为下一个遍历的节点，向上回溯
* 直到当前结点是其父节点的左孩子时停止
* 直到找到一个父节点X，并且这个父节点X是其本身的父节点Y的左孩子为止
*/
public void test4() {
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);
TreeLinkNode node8 = new TreeLinkNode(8);
node1.left = node2;
node1.right = node3;
node2.next = node1;
node3.next = node1;
node2.left = node4;
node2.right = node5;
node4.next = node2;
node5.next = node2;
node4.left = node6;
node4.right = node7;
node6.next = node4;
node7.next = node4;
node5.right = node8;
node8.next=node5;
TreeLinkNode nextNodeOf1=GetNext(node8);
if(nextNodeOf1!=null)
System.out.println("8结点的下一个结点值为："+nextNodeOf1.val);
else
System.out.println("8结点无下一结点");
}
}
————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。
京公网安备 11010502036488号