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.
分析:
iterative的解法需要记得,insert总是发生在leaf上面,于是可以这么做,都第二遍了,还不会
解法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;
}
TreeNode curr = root;
TreeNode prev = null;
while (curr != null) {
prev = curr;
if (node.val < curr.val) {
curr = curr.left;
} else {
curr = curr.right;
}
}
if (node.val < prev.val) {
prev.left = node;
} else {
prev.right = node;
}
return root;
}
}
解法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) {
// write your code here
if (root == null) {
return node;
}
if (node.val < root.val) {
root.left = insertNode(root.left, node);
} else {
root.right = insertNode(root.right, node);
}
return root;
}
}