2 ❌ 的插入操作

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        // root = insertIntoBST2(root, val);    //迭代
        // if (root.val < val) {                //递归
        //     root.right = insertIntoBST(root.right, val);
        // } else {
        //     root.left = insertIntoBST(root.left, val);
        // }
        return root;
    }
    public TreeNode insertIntoBST2(TreeNode root, int val){     //迭代
        TreeNode node = new TreeNode(val);
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode cur = root;    //从根节点开始找
        
        while(true){
            int cmp = val - cur.val;
            if (cmp < 0){                //待插入值比当前结点值小
                if (cur.left == null){    //如果当前结点是叶子结点，则添加到当前结点的左子树处
                    cur.left = node;
                    break;
                }
                cur = cur.left;
            }else{                        //待插入值比当前结点值大
                if (cur.right == null){//如果当前结点是叶子结点，则添加到当前结点的右子树处
                    cur.right = node;
                    break;
                }
                cur = cur.right;
            }
        }
        // while (true) {
        //     if (cur.val > val) {
        //         if (cur.left == null) {
        //             cur.left = node;
        //             break;
        //         }
        //         cur = cur.left;
        //     } else {
        //         if (cur.right == null) {
        //             cur.right = node;
        //             break;
        //         } 
        //         cur = cur.right;
        //     }
        // }
        return root;
    }
}