# 狗家电面

``````   A                    C
/  \                  / \
B   C   ==>           D   B
\                     \
D                    A
``````

``````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);
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;
}

``````

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

deserize and reshuffe?

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