非死不可 热乎昂赛面经 NEW GRAD

二差树转双向linked list
https://www.youtube.com/watch?v=Dte6EF1nHNo

  

1. //left = next; right = prev; head->prev = tail
   
2. pair<TreeNode*,TreeNode*> helper(TreeNode* root) {// return {head, tail}
   
3.     if (root == NULL || (root->left == NULL && root->right == NULL)) return make_pair(root,root);
   
4.     pair<TreeNode*,TreeNode*> l = helper(root->left);
   
5.     pair<TreeNode*,TreeNode*> r = helper(root->right);
   
6.     //head = l.first; tail = r.second
   
7.     root->left = l.second;
   
8.     if (l.second)l.second->right = root;
   
9.     root->right = r.first;
   
10.     if (r.first) r.first->left = root;
    
11.     return make_pair(l.first, r.second);
    
12. }
    
13. TreeNode* bt2dl(TreeNode* root) {
    
14.     return helper(root).first;
    
15. }

复制代码

edyyy 发表于 2018-4-15 10:38

50   TreeNode * n25 = new TreeNode (25);
51   TreeNode * n30 = new TreeNode (30);
52   TreeNode * n11 = new TreeNode (11);
53   n30->left = n11;
54   TreeNode * n12 = new TreeNode (12);
55   n12->left = n25;
56   n12->right = n30;
57   TreeNode * n15 = new TreeNode (15);
58   TreeNode * n36 = new TreeNode (36);
59   n15->left = n36;
60   TreeNode * n10 = new TreeNode (10);
61   n10->left = n12;
62   n10->right = n15;


这样的test case 过不了啊

ohshout 发表于 2018-4-16 05:42
50   TreeNode * n25 = new TreeNode (25);
51   TreeNode * n30 = new TreeNode (30);
52   TreeNo ...

用iterative写，很清晰。如果你用recursive的话，让你的helper function return the last node connected. 比如 leftResult = helper(node.left), 然后leftResult.next = node, node.prev = leftResult. 然后rightResult =  helper(node.right), return rightResult == null ? node : rightResult;

taoli0515 发表于 2018-4-15 03:49
按照层主的思路 似乎不需要union find，凡是element对应两个及以上的set id就union,这里如何输出结果呢?

我细细想了想，细节上确实有问题。因为我和面试官最后讨论的是output的时候。之前还是需要Union find来合并。只是最后Output的时候，不需要查到root，只需要查到parent就行了，直接加到parent的set里。

[x’s < smaller, smaller, smaller <= x’s < larger, larger, x’s >= larger] LZ能详细讲一下这个题目意思吗

请问你说的shadow是什么意思啊