狗家电面

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. }

复制代码

递归思路这题不难。

每一个子问题的操作是，当前node，左node，右node，旋转一下。只旋转三个Node，不改变sub tree
bottom up的方式，一直递归解决。最后是root。返回tree即可