微软电面

是一个很友好的印度哥们电面的我。先随便扯了点经历，题目是从一颗二叉排序树中删除小于low_value或者大于high_value的节点。

因为面试前几天我看过从二叉排序树中删除节点的题，所以就机械的套用了那个题的思路，采用top down的方式，迭代的删除符合条件的node，然后用比这个节点略大的节点来代替本节点。估计是印度哥们刚开始也觉得这样

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

]



补充内容 (2020-2-20 13:38):
第23行应该是  parent->left = cur->right;

写了个c++版本

1. node* TruncateBST(node *root, int min, int max) {
   
2.     if(!root)
   
3.     return NULL;
   
4.    
   
5.     if(root->val < min)
   
6.         return TruncateBST(root->right, min, max);
   
7.     if(root->val > max)
   
8.         return TruncateBST(root->left, min, max);
   
9.         
   
10.     root->left = TruncateBST(root->left, min, max);
    
11.     root->right = TruncateBST(root->right, min, max);
    
12.     return root;
    
13. }

复制代码

这个Java版本的怎么样？

1. public Node removeNodesLargerThan(Node root, int target) {
   
2.         if (root == null) {
   
3.             return null;
   
4.         }
   
5.         if (target < root.value) {
   
6.             Node realRoot = removeNodesLargerThan(root.left, target);
   
7.             root.left = null;
   
8.             return realRoot;
   
9.         } else if (target > root.value) {
   
10.             Node realRight = removeNodesLargerThan(root.right, target);
    
11.             root.right = realRight;
    
12.             return root;
    
13.         } else {
    
14.             root.right = null;
    
15.             return root;
    
16.         }
    
17.     }

复制代码

jackjob 发表于 2020-2-16 12:50
这个Java版本的怎么样？
[mw_shl_code=java,true]public Node removeNodesLargerThan(Node root, int targ ...

显然不对啊

同学你这个所谓的bottom up/top down的说法看的我是云里雾里

spirit_room 发表于 2020-2-17 03:59
显然不对啊

怎么不对了？

jackjob 发表于 2020-2-19 05:20
怎么不对了？

要求是删除某个范围的，不是等于某个数值的，你再仔细看看