85. Insert Node in a Binary Search Tree【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.

Notice

You can assume there is no duplicate values in this tree + node.

Example

Given binary search tree as follow, after Insert node 6, the tree should be:

  2             2
 /            / 
1   4   -->   1   4
   /             /  
  3             3   6

Challenge

Can you do it without recursion?

解法一：

 1 public class Solution {
 2     /**
 3      * @param root: The root of the binary search tree.
 4      * @param node: insert this node into the binary search tree
 5      * @return: The root of the new binary search tree.
 6      */
 7     public TreeNode insertNode(TreeNode root, TreeNode node) {
 8         if (root == null) {
 9             return node;
10         }
11         if (root.val > node.val) {
12             root.left = insertNode(root.left, node);
13         } else {
14             root.right = insertNode(root.right, node);
15         }
16         return root;
17     }
18 }

解法二：

 1 public class Solution {
 2     /**
 3      * @param root: The root of the binary search tree.
 4      * @param node: insert this node into the binary search tree
 5      * @return: The root of the new binary search tree.
 6      */
 7     public TreeNode insertNode(TreeNode root, TreeNode node) {
 8         if (root == null) {
 9             root = node;
10             return root;
11         }
12         TreeNode tmp = root;
13         TreeNode last = null;
14         while (tmp != null) {
15             last = tmp;
16             if (tmp.val > node.val) {
17                 tmp = tmp.left;
18             } else {
19                 tmp = tmp.right;
20             }
21         }
22         if (last != null) {
23             if (last.val > node.val) {
24                 last.left = node;
25             } else {
26                 last.right = node;
27             }
28         }
29         return root;
30     }
31 }

解法三：

 1 class Solution {
 2 public:
 3     /*
 4      * @param root: The root of the binary search tree.
 5      * @param node: insert this node into the binary search tree
 6      * @return: The root of the new binary search tree.
 7      */
 8     TreeNode * insertNode(TreeNode * root, TreeNode * node) {
 9         stack<TreeNode * > sta;
10         sta.push(root);
11         TreeNode * last = NULL;
12         while (sta.size() != 0) {
13             TreeNode * now = sta.top();
14             sta.pop();
15             if (now == NULL) {
16                 if (last == NULL) {
17                     root = node;
18                 } else if (last->val <= node->val) {
19                     last -> right = node;
20                 } else {
21                     last -> left = node;
22                 }
23                 break;
24             } else if (now->val <= node->val) {
25                 sta.push(now->right);
26             } else {
27                 sta.push(now->left);
28             }
29             last = now;
30         }
31         return root;
32     }
33 };

参考@DLNU-linglian 的代码