剑指Offer面试题：7.二叉树的下一个结点

一、题目
————————————————
给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？ 树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。
————————————————
二、思路
————————————————
首先自己在草稿纸上画图，进行分析（不再展开）。可以发现下一个结点的规律为：
　　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结点无下一结点");
    }
}

————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。