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.

Have you met this question in a real interview? 

Yes

Example

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

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

解法一，用pointer of pointer。。。有点恶心。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

/** * 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) { // write your code here insert(&root, node); return root; } void insert(TreeNode** root, TreeNode* node){ if (!*root){ *root=node; return; } TreeNode* r=*root; if (node->val<r->val){ insert(&r->left, node); } else{ insert(&r->right,node); } } };

解法二，

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

/** * 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) { // write your code here return insert(root,node); } TreeNode* insert(TreeNode* root, TreeNode* node){ if (!root) return node; if (node->val<root->val) root->left=insert(root->left, node); else root->right=insert(root->right,node); return root; } };