朋友内推，2/28电面。一个国人大哥，没有问其他，直接上题。给一个二叉树，随机改变每个node的位置，新的树结构不变，要保证每个node跟以前的该位置node不一样，不能直接更换node的value。
A C
/ \ / \
B C ==> D B
\ \
D A
题刷的还是不够，临场反应也慢。讲了半天我的思路，时间过了大半了，他还是没太明白我的思路，大哥人很好，又多给了些时间写code，不过也没写好。应该是跪了，机会就这么浪费了。
题没刷多少，不知道有没有人见过这个，大家可以讨论下。
感觉就是建一个tree node wrapper node把原节点包进去，然后遍历原树通过wrapper把原来树的结构记录下来，然后第二次遍历wrapper tree就不需要原来的树的信息了，随机取一个当前可用的节点然后重新分配左右子节点。
private class WrapperNode {
TreeNode node;
WrapperNode left;
WrapperNode right;
public WrapperNode(TreeNode node) {
this.node = node;
this.left = null;
this.right = null;
}
}
public TreeNode shuffleTreeNodes(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
WrapperNode wroot = buildWrapperTree(root, list);
Collections.shuffle(list);
return shuffleTree(wroot, list.iterator());
}
private WrapperNode buildWrapperTree(TreeNode root, List<TreeNode> list) {
if (root == null) {
return null;
}
WrapperNode wroot = new WrapperNode(root);
list.add(root);
WrapperNode left = buildWrapperTree(root.left, list);
WrapperNode right = buildWrapperTree(root.right, list);
wroot.left = left;
wroot.right = right;
return wroot;
}
private TreeNode shuffleTree(WrapperNode wroot, Iterator<TreeNode> it) {
if (wroot == null) {
return null;
}
TreeNode left = shuffleTree(wroot.left, it);
TreeNode right = shuffleTree(wroot.right, it);
TreeNode root = it.next();
root.left = left;
root.right = right;
return root;
}
感谢，但是不是很明白怎么样个随机法
这个题肯定没有要求inpalce吧
这个要自己来设计，需保证每个Node跟原来的不一样，随机的意思就是运行了这个程序多次，但每次的结果可能是不一样的。
没有。我那时候的思路是pre order出来每个node，针对每个node的左右孩子，随机找到后面的一个node的孩子交换。针对叶子节点特殊处理下。不过感觉跟面试官不是一个思路。
binary tree 有pre order 和in order一起就能决定一棵树的结构，可以吧preorder 和in order 存下来。确定subtree 的range 然后shuffle 重新构建树。
我觉得可以用post order读然后用pre order存就可以了
deserize and reshuffe?
我的in-place思路：
我觉得你是不是对题意有些误解，不能换node里面的值，要直接换node，听起来就怪怪的。