Insert Node in a Binary Search Tree
Source
- lintcode: (85) Insert Node in a Binary Search Tree
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:
2
/ \
1 4
/
3
after Insert node 6, the tree should be:
2
/ \
1 4
/ \
3 6
Challenge
Do it without recursion
题解 - 递归
二叉树的题使用递归自然是最好理解的，代码也简洁易懂，缺点就是递归调用时栈空间容易溢出，故实际实现中一般使用迭代替代递归，性能更佳嘛。不过迭代的缺点就是代码量稍(很)大，逻辑也可能不是那么好懂。
既然确定使用递归，那么接下来就应该考虑具体的实现问题了。在递归的具体实现中，主要考虑如下两点：
- 基本条件/终止条件 - 返回值需斟酌。
- 递归步/条件递归 - 能使原始问题收敛。
首先来找找递归步，根据二叉查找树的定义，若插入节点的值若大于当前节点的值，则继续与当前节点的右子树的值进行比较；反之则继续与当前节点的左子树的值进行比较。题目的要求是返回最终二叉搜索树的根节点，从以上递归步的描述中似乎还难以对应到实际代码，这时不妨分析下终止条件。
有了递归步，终止条件也就水到渠成了，若当前节点为空时，即返回结果。问题是——返回什么结果？当前节点为空时，说明应该将「插入节点」插入到上一个遍历节点的左子节点或右子节点。对应到程序代码中即为root->right = node或者root->left = node. 也就是说递归步使用root->right/left = func(...)即可。
C++ Recursion
/**
* forked from http://www.jiuzhang.com/solutions/insert-node-in-binary-search-tree/
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @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.
*/
TreeNode* insertNode(TreeNode* root, TreeNode* node) {
if (NULL == root) {
return node;
}
if (node->val <= root->val) {
root->left = insertNode(root->left, node);
} else {
root->right = insertNode(root->right, node);
}
return root;
}
};
Java Recursion
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) {
if (root == null) {
return node;
}
if (root.val > node.val) {
root.left = insertNode(root.left, node);
} else {
root.right = insertNode(root.right, node);
}
return root;
}
}
题解 - 迭代
看过了以上递归版的题解，对于这个题来说，将递归转化为迭代的思路也是非常清晰易懂的。迭代比较当前节点的值和插入节点的值，到了二叉树的最后一层时选择是链接至左子结点还是右子节点。
C++
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @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.
*/
TreeNode* insertNode(TreeNode* root, TreeNode* node) {
if (NULL == root) {
return node;
}
TreeNode* tempNode = root;
while (NULL != tempNode) {
if (node->val <= tempNode->val) {
if (NULL == tempNode->left) {
tempNode->left = node;
return root;
}
tempNode = tempNode->left;
} else {
if (NULL == tempNode->right) {
tempNode->right = node;
return root;
}
tempNode = tempNode->right;
}
}
return root;
}
};
源码分析
在NULL == tempNode->right或者NULL == tempNode->left时需要在链接完node后立即返回root，避免死循环。
Java Iterative
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 (root == null) return node;
if (node == null) return root;
TreeNode rootcopy = root;
while (root != null) {
if (root.val <= node.val && root.right == null) {
root.right = node;
break;
}
else if (root.val > node.val && root.left == null) {
root.left = node;
break;
}
else if(root.val <= node.val) root = root.right;
else root = root.left;
}
return rootcopy;
}
}