Lintcode85 Insert Node In A Binary Search Tree solution 题解
Aug 22, 2017 · 2 min read
【题目描述】
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.
给定一棵二叉查找树和一个新的树节点,将节点插入到树中。
你需要保证该树仍然是一棵二叉查找树。
【注】:可以假设此树结点中没有重复值。
【题目链接】
www.lintcode.com/en/problem/insert-node-in-a-binary-search-tree/
【题目解析】
首先要明确一个事实:节点一定是被插在二叉搜索树的叶子节点后的,知道了这个事实,就好办了。可以使用DFS,DFS时每次将当前节点的值与node的值作比较,如果比node小就往右走,否则往左走,直到叶子节点。为了方便最后的插入操作,需要用一个变量记录上一次访问的节点。
【参考答案】
www.jiuzhang.com/solutions/insert-node-in-a-binary-search-tree/
