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
