PattySung

Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]

Example 3:

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

<解題>

如果本身為空：if(root == null) return new TreeNode(val);
建立一個新的TreeNode current_node = root; 作為操作
判斷current_node與val的大小，是否為空，做調整與加入
return root


class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
        
        TreeNode current_node = root;
        while(true){
            if(current_node.val <= val){
                if(current_node.right != null ){
                    current_node = current_node.right;
                } else{
                    current_node.right = new TreeNode(val);
                    break;
                }
            }else{
                if(current_node.left != null ){
                    current_node = current_node.left;
                } else{
                    current_node.left = new TreeNode(val);
                     break;
                }
            }
        }
        return root;
    }
}

Time: O(log n) Space: O(1)

Leetcode-701. Insert into a Binary Search Tree

<解題>