public class Test21 {
    //二叉树，left right parent父节点指针
    //返回输入节点在这个树中序遍历序列里下一个节点

    static class TreeNode {
        int val;
        TreeNode parent, left, right;

        public TreeNode(int val, TreeNode parent, TreeNode left, TreeNode right) {
            this.val = val;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }

    public static TreeNode findNextNodeInMidSec(TreeNode now) {
        if (now == null) {
            return null;
        }

        if (now.right != null) {
            TreeNode treeNode = now.right;
            while (treeNode.left != null) {
                treeNode = treeNode.left;
            }
            return treeNode;
        }

        while (now.parent != null && now.parent.right == now) {
            now = now.parent;
        }
        return now.parent;
    }

//        1
//       / \
//      2   3
//         / \
//        4   5

    //21435
    public static void main(String[] args) {
        TreeNode n5 = new TreeNode(5, null, null, null);
        TreeNode n4 = new TreeNode(4, null, null, null);
        TreeNode n3 = new TreeNode(3, null, n4, n5);
        n5.parent = n3;
        n4.parent = n3;
        TreeNode n2 = new TreeNode(2, null, null, null);
        TreeNode n1 = new TreeNode(1, null, n2, n3);
        n2.parent = n1;
        n3.parent = n1;

        TreeNode find4 = findNextNodeInMidSec(n4);
        System.out.println(find4.val);
        TreeNode find3 = findNextNodeInMidSec(n3);
        System.out.println(find3.val);
        TreeNode find2 = findNextNodeInMidSec(n2);
        System.out.println(find2.val);
        TreeNode find1 = findNextNodeInMidSec(n1);
        System.out.println(find1.val);
        TreeNode find5 = findNextNodeInMidSec(n5);
        System.out.println(find5 == null);

        TreeNode findX = findNextNodeInMidSec(null);
        System.out.println(findX == null);
    }
}