Insert Node in a Binary Search Tree

今天是一道有关链表的题目，来自LintCode，难度为Easy。

题目如下

Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tree.
Example
Given binary search tree as follow, after Insert node 6, the tree should be:

二叉树

解题思路及代码见阅读原文

回复0000查看更多题目

解题思路

首先，该题的难度为简单。但当开始看到该题时，并没有这种感觉，因为考虑到要插入的节点与已经存在的节点的值相同。

但是，在抱着尝试的心态提交了没有处理这种情况的代码时，居然通过了，说明这里要插入的节点是没有相同的值的。

所以这道题就变成Easy了，思路也很简单：

从头节点开始，比较要插入的值和该节点的值，若比该节点的值大，则继续比较右节点，反之比较左节点。直到其左子树或右子树为空，在该位置插入该节点。

最后，有了思路我们来看代码。

代码如下

Java版

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param node: insert this node into the binary search tree
     * @return: The root of the new binary search tree.
     */
    public TreeNode insertNode(TreeNode root, TreeNode node) {
        // write your code here
        if(null == root)
                return node;
            if(null == node)
                return root;
            TreeNode cur = root, prev = root;
            while(cur != null) {
                prev = cur;
                if(node.val > cur.val) {
                    cur = cur.right;
                } else {
                    cur = cur.left;
                }
            }
            if(node.val > prev.val)
                prev.right = node;
            else
                prev.left = node;
            return root;
    }
}

关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助

image