狗家电面

允许space么？允许的话那可以用serialize出来然后换一下位置然后deserialize回去

或者能不能用蓄水池取样 就是每次决定「换不换」有一定的几率？

感觉就是建一个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.     }

复制代码

traverse, hash and shuffle
inorder traverse
hash inorder indexes to nodes
fisher-yates shuffle

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

请问下po主，你是否没有考虑到“每个node跟以前的该位置node不一样”这个条件？我试着run了一下你的代码，似乎有时会出现一个node位置没变的情况。你觉得如果要完成这个要求的话，还能用recursive的方法么？

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

啊我想清楚了，应该是可以的。打扰了

yangdaxian 发表于 2018-6-5 02:46
啊我想清楚了，应该是可以的。打扰了

hello, 我也有相同的疑惑。。假如level order是A,B,C,#, #, #,D这样的结构，用这个方法做出来的我觉得是D,A,C,#,#,#,B，这样的话C这个位置就没有变啊。。

bunnyhuhu 发表于 2018-6-5 11:56
hello, 我也有相同的疑惑。。假如level order是A,B,C,#, #, #,D这样的结构，用这个方法做出来的我觉得是D ...

他的code里有一个shuffle，但是不能保证让每个点都变化位置。但要解决也比较简单，就多shuffle几次直到满足要求就可以了。另外就是40行应该放在38行，38和39放在39，40行，这样保证两次遍历的顺序是一样的，就可以满足题目要求。

额  我有两个很思路，此题真的有点难度:
解法1, deserialize  树   然后更换相应节点  再 serialize 树  但是这个解法应该不是面试官想要的 因为效率太低了
解法2，找到两个点各自的parent node, 然后做交换 。。。

能否这样：
1. 先inorder遍历树一遍把节点存在list里一共n个节点
2. 再inorder遍历把数的结构复制下来，复制树的每个节点的值对应遍历的顺序0...n
3. 把list里的点shuffle
4. 再遍历复制树，根据复制树的值（对应list里的index值）把list里的点重新连一遍
5. 返回list.get(0)

多谢分享