狗家电面

朋友内推，2/28电面。一个国人大哥，没有问其他，直接上题。给一个二叉树，随机改变每个node的位置，新的树结构不变，要保证每个node跟以前的该位置node不一样，不能直接更换n

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

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

好。应该是跪了，机会就这么浪费了。
题没刷多少，不知道地里有没有人见过这个，大家可以讨论下。

感觉就是建一个tree node wrapper node把原节点包进去，然后遍历原树通过wrapper把原来树的结构记录下来，然后第二次遍历wrapper tree就不需要原来的树的信息了，随机取一个当前可用的节点然后重新分配左右子节点。

1. private class WrapperNode {
   
2.         TreeNode node;
   
3.         WrapperNode left;
   
4.         WrapperNode right;
   
5. 
   
6.         public WrapperNode(TreeNode node) {
   
7.             this.node = node;
   
8.             this.left = null;
   
9.             this.right = null;
   
10.         }
    
11.     }
    
12. 
    
13. 
    
14.     public TreeNode shuffleTreeNodes(TreeNode root) {
    
15.         List<TreeNode> list = new ArrayList<>();
    
16.         WrapperNode wroot = buildWrapperTree(root, list);
    
17.         Collections.shuffle(list);
    
18.         return shuffleTree(wroot, list.iterator());
    
19.     }
    
20. 
    
21.     private WrapperNode buildWrapperTree(TreeNode root, List<TreeNode> list) {
    
22.         if (root == null) {
    
23.             return null;
    
24.         }
    
25.         WrapperNode wroot = new WrapperNode(root);
    
26.         list.add(root);
    
27.         WrapperNode left = buildWrapperTree(root.left, list);
    
28.         WrapperNode right = buildWrapperTree(root.right, list);
    
29.         wroot.left = left;
    
30.         wroot.right = right;
    
31.         return wroot;
    
32.     }
    
33. 
    
34.     private TreeNode shuffleTree(WrapperNode wroot, Iterator<TreeNode> it) {
    
35.         if (wroot == null) {
    
36.             return null;
    
37.         }
    
38.         TreeNode left = shuffleTree(wroot.left, it);
    
39.         TreeNode right = shuffleTree(wroot.right, it);
    
40.         TreeNode root = it.next();
    
41.         root.left = left;
    
42.         root.right = right;
    
43.         return root;
    
44.     }

复制代码

littledog 发表于 2018-3-28 07:18
感觉就是建一个tree node wrapper node把原节点包进去，然后遍历原树通过wrapper把原来树的结构记录下来， ...

为什么要新建一个wrapper node 类呢？用原treenode 也可以做吧？跑了一下感觉差不多

1. class Solution {
   
2.     public TreeNode shuffleTreeNodes(TreeNode root) {
   
3.         List<TreeNode> list = new ArrayList<>();
   
4.         // 建一棵与原树结构完全一样的树
   
5.         TreeNode structureRoot = buildStructure(root, list);
   
6.         Collections.shuffle(list);
   
7.         // 用原结点按照结构树重构一棵树
   
8.         return shuffleTree(structureRoot, list.iterator());
   
9.     }
   
10. 
    
11.     private TreeNode buildStructure(TreeNode root, List<TreeNode> list) {
    
12.         if (root == null) {
    
13.             return null;
    
14.         }
    
15.         
    
16.         list.add(root);
    
17.         TreeNode structureRoot = new TreeNode(-1);
    
18.         structureRoot.left = buildStructure(root.left, list);
    
19.         structureRoot.right = buildStructure(root.right, list);
    
20.         return structureRoot;
    
21.     }
    
22. 
    
23.     private TreeNode shuffleTree(TreeNode structureRoot, Iterator<TreeNode> it) {
    
24.         if (structureRoot == null) {
    
25.             return null;
    
26.         }
    
27.         
    
28.         TreeNode root = it.next();
    
29.         root.left = shuffleTree(structureRoot.left, it);
    
30.         root.right = shuffleTree(structureRoot.right, it);
    
31.         return root;
    
32.     }
    
33. }

复制代码

感谢，但是不是很明白怎么样个随机法

这个题肯定没有要求inpalce吧

buranmilk4 发表于 2018-3-3 01:13
感谢，但是不是很明白怎么样个随机法

这个要自己来设计，需保证每个Node跟原来的不一样，随机的意思就是运行了这个程序多次，但每次的结果可能是不一样的。

billb 发表于 2018-3-3 01:31
这个题肯定没有要求inpalce吧

没有。我那时候的思路是pre order出来每个node，针对每个node的左右孩子，随机找到后面的一个node的孩子交换。针对叶子节点特殊处理下。不过感觉跟面试官不是一个思路。

binary tree 有pre order 和in order一起就能决定一棵树的结构，可以吧preorder 和in order 存下来。确定subtree 的range 然后shuffle 重新构建树。

yzkst06100 发表于 2018-3-3 02:18
binary tree 有pre order 和in order一起就能决定一棵树的结构，可以吧preorder 和in order 存下来。确定su ...

我觉得可以用post order读然后用pre order存就可以了

deserize and reshuffe?

我的in-place思路：
1. 先用中序遍历把所有原树的值记在一个数组里
2. 把这个array shuffle
3. 重新对原树进行中序遍历，依次填入shuffle后的值

我觉得你是不是对题意有些误解，不能换node里面的值，要直接换node，听起来就怪怪的。