//2种解法 1.循环
// 2.递归
public class _998 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

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

    static class Solution1 {
        class Solution {
            public TreeNode insertIntoMaxTree(TreeNode root, int val) {
                //分情况讨论
                //1. 当前节点大于根节点
                //2. 当前节点大于根右子树的根
                TreeNode cur = new TreeNode(val);
                TreeNode right = root;
                TreeNode p = null;
                while (right != null && right.val > cur.val) {
                    p = right;
                    right = right.right;
                }
                if (p != null) {
                    p.right = cur;
                }
                cur.left = right;
                return right == root ? cur : root;
            }
        }
    }

    static class Solution2 {
        public TreeNode insertIntoMaxTree(TreeNode root, int val) {
            //递归
            // 1. 如果直接插入则返回cur
            if (root == null || val > root.val) {
                TreeNode cur = new TreeNode(val);
                cur.left = root;
                return cur;
            }
            root.right = insertIntoMaxTree(root.right, val);
            return root;
        }
    }
}