脚本宝典收集整理的这篇文章主要介绍了[LintCode] Insert Node in a Binary Search Tree，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
PRoblem
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:
2 2
/ /
1 4 --> 1 4
/ /
3 3 6
Challenge
Can you do it without recursion?
Note
建立两个树结点，先用cur找到node在BST的位置，让pre作为cur的根节点；找到node的位置后，cur指向null。此时，用node代替cur与pre连接就可以了。返回root。
Solution
public class Solution {
public TreeNode insertNode(TreeNode root, TreeNode node) {
if (root == null) return node;
TreeNode cur = root, pre = null;
while (cur != null) {
pre = cur;
if (cur.val > node.val) cur = cur.left;
else cur = cur.right;
}
if (pre != null) {
if (pre.val > node.val) pre.left = node;
else pre.right = node;
}
return root;
}
}以上是脚本宝典为你收集整理的[LintCode] Insert Node in a Binary Search Tree全部内容，希望文章能够帮你解决[LintCode] Insert Node in a Binary Search Tree所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。