Bloomberg电面

1. BST第二

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

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

ak

lcq123 发表于 2017-9-22 22:43
BST第二大的数 请问楼主能详细说一下吗？

BST从root开始一路往右root = root.right, 一直到root.right == null，root.val就是最大的数。
最大的数如果有left children，root.left != null，从root.left开始一路往右，最后一个就是第二大的数。
如果没有left children， root.left == null，它的parent是第二大的数root.parent.val。一路往右时存个parent。

xinqiji1992 发表于 2017-9-23 06:09
求问楼主iterative要怎么做呢？

就是和iterative inorder traversal很像，只不过想right后left，大概代码是这样的
int second_large(TreeNode* root) {
            if (!root || (!root->left&& !root->right)) return 0;
            TreeNode* cur = root;
            stack<TreeNode*> st;
            int c = 0;
            while (cur || !st.empty()) {
                    while (cur) {
                            st.push(cur);
                            cur = cur->right;
                    }
                    cur = st.top();
                    st.pop();
                    c++;
                    if (c == 2) break
                    res.push_back(cur->val);
                    cur = cur->left;
            }
            return cur->val;
    }

感觉这个样子做？
void helper(TreeNode* root,int &res, int& cnt){
          if(root==NULL) return;
          helper(root->right);
          cnt++;
          if(cnt==2){
            res=root->val;
            return;
          }
          helper(root->left);
    }

补充内容 (2017-12-3 15:49):
第三行跟最后一行call helper function少了res,cnt参数。。。

謝謝分享
第一題lc有嗎？

BST第二大的数 请问楼主能详细说一下吗？

mikemike0 发表于 2017-9-22 22:41
謝謝分享
第一題lc有嗎？

貌似没有的

lcq123 发表于 2017-9-22 22:43
BST第二大的数 请问楼主能详细说一下吗？

就是BST是有序的，然后找到第二大的那个，但是说两种方法，recursive或者iteratiive来做，就是inorder的变形吧，也可以记录parent来做，方法挺多的

shawnzhao 发表于 2017-9-23 01:32
就是BST是有序的，然后找到第二大的那个，但是说两种方法，recursive或者iteratiive来做，就是inorder的 ...

好的，谢谢楼主！

lcq123 发表于 2017-9-23 01:35
好的，谢谢楼主！

不客气，加油啊

shawnzhao 发表于 2017-9-23 01:32
就是BST是有序的，然后找到第二大的那个，但是说两种方法，recursive或者iteratiive来做，就是inorder的 ...

求问楼主iterative要怎么做呢？