c****e
发帖数: 398 | 1 第一轮一小时面试，白板题：
Binary Tree 里有重复的值，只会出现当前点的右侧，怎么删掉
有几个解法：
1. O(nlgn) time, O(1) space，从每个点开始遍历右边，删掉重复点
2. O(n) time, O(n) space，建map
3. O(n) time, O(1) space，Morris Traversal
最好的解法自然是3，但还是紧张，第一反应是解法1
写完聊天的时候说有一个解法是线性时间，常量空间的时候突然想起来，感觉自己略蠢 |
T****U
发帖数: 3344 | 2 morris只是省掉了stack, 你还是需要map
Binary Tree 里有重复的值，只会出现当前点的右侧 是指两个重复的值，一个在另一
个的右子树上吗？还是指重复的值，一个必然是另一个的右子节点？ |
s***3
发帖数: 42 | 3 听描述像是右子树。
【在 T****U 的大作中提到】
: morris只是省掉了stack, 你还是需要map
: Binary Tree 里有重复的值，只会出现当前点的右侧 是指两个重复的值，一个在另一
: 个的右子树上吗？还是指重复的值，一个必然是另一个的右子节点？
|
c****e
发帖数: 398 | 4 可以有无数个duplicate，但是都只会出现在右边，对于左边是严格大于的
【在 T****U 的大作中提到】
: morris只是省掉了stack, 你还是需要map
: Binary Tree 里有重复的值，只会出现当前点的右侧 是指两个重复的值，一个在另一
: 个的右子树上吗？还是指重复的值，一个必然是另一个的右子节点？
|
T****U
发帖数: 3344 | 5 删除节点你怎么做到O(1)?
【在 c****e 的大作中提到】
: 可以有无数个duplicate，但是都只会出现在右边，对于左边是严格大于的
|
l**********1
发帖数: 1 | 6 请问这个binary tree是类似于BST吗？就是说是不是左子树的值都小于root的值，有字
数的值都大于等于root的值，如果是的话就比较简
public void deleteDuplicate(TreeNode root){
if(root == null){
return;
}
deleteDuplicate(root.left);
while(root.right != null && root.right.val == root.val){
root.right = root.right.right;
}
deleteDuplicate(root.right);
}
求指正 |
v**N
发帖数: 11 | 7 如果balanced的话,time logn, space logn,
同意否? |
i*****h
发帖数: 1534 | 8 看着挺讨巧的，坐等解答
【在 l**********1 的大作中提到】
: 请问这个binary tree是类似于BST吗？就是说是不是左子树的值都小于root的值，有字
: 数的值都大于等于root的值，如果是的话就比较简
: public void deleteDuplicate(TreeNode root){
: if(root == null){
: return;
: }
: deleteDuplicate(root.left);
: while(root.right != null && root.right.val == root.val){
: root.right = root.right.right;
: }
|
