解题思路

因为是二叉搜索树(Binary search tree),整个树是有序的，我们根据val来调整自己下一个要遍历的节点，若下一个节点为为空，则创立新节点，将节点插入即可.

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None: return TreeNode(val)
        self.dfs(root, val)
        return root
    def dfs(self, root, val):
        if root.val > val and root.left:
            self.dfs(root.left, val)
        elif root.val < val and root.right:
            self.dfs(root.right, val)
        elif root.val > val and root.left is None:
            root.left = TreeNode(val)
        else:
            root.right = TreeNode(val)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) return new TreeNode(val);
        dfs(root, val);
        return root;
    }
    void dfs(TreeNode* node, int val) {
        if (node->val > val && node->left != NULL) dfs(node->left, val);
        else if (node->val < val && node->right != NULL) dfs(node->right, val);
        if (node->val > val && node->left == NULL) node->left = new TreeNode(val);
        else if (node->val < val && node->right == NULL) node->right = new TreeNode(val);
    }
};

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {return &TreeNode{Val: val}}
    dfs(root, val)
    return root
}
func dfs(node *TreeNode, val int) {
    if node.Val > val && node.Left != nil {dfs(node.Left, val)}
    if node.Val < val && node.Right != nil {dfs(node.Right, val)}

    if node.Val > val && node.Left == nil {node.Left = &TreeNode{Val: val}}
    if node.Val < val && node.Right == nil {node.Right = &TreeNode{Val: val}}
}