二叉树的下一个结点

题目

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路

这道题思路捋清楚，还是很简单的。

我们以上图为例进行讲解，上图二叉树的中序遍历是d,b,h,e,i,a,f,c,g。我们以这棵树为例来分析如何找出二叉树的下一个结点。

如果一个结点有右子树，那么它的下一个结点就是它的右子树的最左子结点。也就是说从右子结点出发一直沿着指向左子树结点的指针，我们就能找到它的下一个结点。例如，图中结点b的下一个结点是h，结点a的下一个结点是f。

接着我们分析一下结点没有右子树的情形。如果结点是它父结点的左子结点，那么它的下一个结点就是它的父结点。例如，途中结点d的下一个结点是b，f的下一个结点是c。

如果一个结点既没有右子树，并且它还是父结点的右子结点，这种情形就比较复杂。我们可以沿着指向父结点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点。例如，为了找到结点g的下一个结点，我们沿着指向父结点的指针向上遍历，先到达结点c。由于结点c是父结点a的右结点，我们继续向上遍历到达结点a。由于结点a是树的根结点。它没有父结点。因此结点g没有下一个结点。

牛客网通过代码

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if (pNode == null) {
            System.out.print("结点为null ");
            return null;
        }
        if (pNode.right != null) {
            pNode = pNode.right;
            while(pNode.left!=null)
                pNode=pNode.left;
            return pNode;
        }
        while(pNode.next !=null){
            if(pNode==pNode.next .left)
                return pNode.next;
            pNode=pNode.next;
        }
        return null;
    }
}

代码

public class GetNext {
    public static void main(String[] args) {
        //                            1
        //                  2                   3
        //             4         5          6          7
        //          8     9   10   11   12   13    14   15
        TreeNode n1 = new TreeNode(1); // 12
        TreeNode n2 = new TreeNode(2); // 10
        TreeNode n3 = new TreeNode(3); // 14
        TreeNode n4 = new TreeNode(4); // 9
        TreeNode n5 = new TreeNode(5); // 11
        TreeNode n6 = new TreeNode(6); // 13
        TreeNode n7 = new TreeNode(7); // 15
        TreeNode n8 = new TreeNode(8); // 4
        TreeNode n9 = new TreeNode(9); // 2
        TreeNode n10 = new TreeNode(10); // 5
        TreeNode n11 = new TreeNode(11); // 1
        TreeNode n12 = new TreeNode(12); // 6
        TreeNode n13 = new TreeNode(13); // 3
        TreeNode n14 = new TreeNode(14); // 7
        TreeNode n15 = new TreeNode(15); // null

        assemble(n1, n2, n3, null);
        assemble(n2, n4, n5, n1);
        assemble(n3, n6, n7, n1);
        assemble(n4, n8, n9, n2);
        assemble(n5, n10, n11, n2);
        assemble(n6, n12, n13, n3);
        assemble(n7, n14, n15, n3);
        assemble(n8, null, null, n4);
        assemble(n9, null, null, n4);
        assemble(n10, null, null, n5);
        assemble(n11, null, null, n5);
        assemble(n12, null, null, n6);
        assemble(n13, null, null, n6);
        assemble(n14, null, null, n7);
        assemble(n15, null, null, n7);
        System.out.println("1" +"->"+ getNext(n1));
        System.out.println("2" + "->"+ getNext(n2));
        System.out.println("3" + "->"+ getNext(n3));
        System.out.println("4" + "->"+ getNext(n4));
        System.out.println("5" +"->"+  getNext(n5));
        System.out.println("6" + "->"+ getNext(n6));
        System.out.println("7" + "->"+ getNext(n7));
        System.out.println("8" +"->"+  getNext(n8));
        System.out.println("9" +"->"+  getNext(n9));
        System.out.println("10" +"->"+  getNext(n10));
        System.out.println("11" +"->"+  getNext(n11));
        System.out.println("12" +"->"+  getNext(n12));
        System.out.println("13" +"->"+  getNext(n13));
        System.out.println("14" + "->"+ getNext(n14));
        System.out.println("15" +"->"+  getNext(n15));
    }
    private static void assemble(TreeNode node,
                                 TreeNode left,
                                 TreeNode right,
                                 TreeNode parent) {
        node.left = left;
        node.right = right;
        node.parent = parent;
    }

    public static TreeNode getNext(TreeNode pNode)
    {
        if(pNode == null){
            return null;
        }
        // 保存要查找的下一个节点
        TreeNode target = null;

        if (pNode.right != null) {
            target = pNode.right;
            while (target.left != null) {
                target = target.left;
            }
            return target;
        } else if (pNode.parent != null){
            target = pNode.parent;
            TreeNode cur = pNode;
            // 如果父新结点不为空，并且，子结点不是父结点的左孩子
            while (target != null && target.left != cur) {
                cur = target;
                target = target.parent;
            }
            return target;
        }
        return null;
    }
}

class TreeNode {
    String val;
    TreeNode left = null;
    TreeNode right = null;
    TreeNode father = null;
    public TreeNode(String val) {
        this.val = val;
    }
}
public class NextNode {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode("A");
        TreeNode t2 = new TreeNode("B");
        TreeNode t3 = new TreeNode("C");
        TreeNode t4 = new TreeNode("D");
        TreeNode t5 = new TreeNode("E");
        TreeNode t6 = new TreeNode("F");
        TreeNode t7 = new TreeNode("G");
        TreeNode t8 = new TreeNode("H");
        TreeNode t9 = new TreeNode("I");
        t1.left = t2;
        t1.right = t3;
        t2.father = t1;
        t2.left = t4;
        t2.right = t5;
        t3.father = t1;
        t3.left = t6;
        t3.right = t7;
        t4.father = t2;
        t5.father = t2;
        t5.left = t8;
        t5.right = t9;
        t6.father = t3;
        t7.father = t3;
        t8.father = t5;
        t9.father = t5;
        System.out.println("中序遍历结果：");
        printTree(t1);
        System.out.println();
        TreeNode serch = t1;
        String string = getNext(serch);
        System.out.println(serch.val + "后面的是：" + string);
    }
    public static void printTree(TreeNode root) {
        if (root != null) {
            printTree(root.left);
            System.out.print(root.val + " ");
            printTree(root.right);
        }
    }
    private static String getNext(TreeNode tree) {
        // TODO Auto-generated method stub
        // 如果有右孩子，则下一个节点是右孩子中最左子节点
        TreeNode temp;
        if (tree.right != null) {
            temp = tree.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            return temp.val;
        }
        // 节点是其父节点的左子节点，则下一个节点就是父节点（节点没有右孩子）
        if (tree.father != null && tree.father.left == tree) {
            return tree.father.val;
        }
        // 如果节点是父节点的右子节点（节点没有右孩子）,下一个节点：父节点是其父节点的左孩子
        if (tree.father != null && tree.father.right == tree) {
            temp = tree.father;
            while (temp != null) {
                if (temp.father.left == temp) {
                    return temp.father.val;
                }
                temp = temp.father;
            }
            // 最后没找到的话 就说明这是最后一个，不存在他的下一个了
        }
        return null;
    }
}