狗家电面

Job Hunting Interview
, ,
1

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

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

题刷的还是不够，临场反应也慢。讲了半天我的思路，时间过了大半了，他还是没太明白我的思路，大哥人很好，又多给了些时间写code，不过也没写好。应该是跪了，机会就这么浪费了。
题没刷多少，不知道地里有没有人见过这个，大家可以讨论下。

2

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