117_PopulatingNextRightPointersinEachNodeII记不住标准答案怎么办

1.     public void connect(TreeLinkNode root) {
   
2.         TreeLinkNode head = null;
   
3.         TreeLinkNode pre = null;
   
4.         TreeLinkNode cur = root;
   
5.         while (cur != null) {
   
6.             while (cur != null) {
   
7.                 if (cur.left != null) {
   
8.                     if (pre != null) {
   
9.                         pre.next = cur.left;
   
10.                     } else {
    
11.                         head = cur.left;
    
12.                     }
    
13.                     pre = cur.left;
    
14.                 }
    
15.                 if (cur.right != null) {
    
16.                     if (pre != null) {
    
17.                         pre.next = cur.right;
    
18.                     } else {
    
19.                         head = cur.left;
    
20.                     }
    
21.                     pre = cur.right;
    
22.                 }
    
23.                 cur = cur.next;
    
24.             }
    
25.             cur = head;
    
26.             pre = null;
    
27.             head = null;
    
28.         }
    
29.     }

复制代码

貌似还是高频，三个指针来回弄实在记不住，又没cleaner一点的答案

画图  实在记不住 就放弃 23333 自己 推演一遍  从来不考记住   除了树的各种遍历  和排序 确实需要默写熟练之外  但是也不是先记住 是先理解了  画图 理解了 默写

记不住说明不理解，再多思考思考

啥叫标准答案啊..

你解题思路没有, 就不会做. 你思路呢?

楼主看看这个写法是不是比较容易理解一点.. 虽然代码量稍微多了一点，但 "TreeLevel" 和 "forEachNodeInNextLevel" 这两个用于解耦关键逻辑的模块写出来的话在面试时应该会有相当的加分效果

1. // 用于构造树的一层
   
2. class TreeLevel {
   
3.     private Node head = null;
   
4.     private Node tail = null;
   
5. 
   
6.     public void add(Node node) {
   
7.         if (head == null) {
   
8.             tail = head = node;
   
9.         } else {
   
10.             tail = tail.next = node;
    
11.         }
    
12.     }
    
13. 
    
14.     public Node getHead() {
    
15.         return head;
    
16.     }
    
17. }
    
18. 
    
19. 
    
20. class Solution {
    
21.     public Node connect(Node root) {
    
22.         for (Node levelStart = root; levelStart != null;) {
    
23.             TreeLevel nextLevel = new TreeLevel();
    
24.             // 遍历下一层所有节点并加入到'nextLevel'里面
    
25.             forEachNodeInNextLevel(levelStart, (node) - > nextLevel.add(node));
    
26.             // 进入下一层
    
27.             levelStart = nextLevel.getHead();
    
28.         }
    
29.         return root;
    
30.     }
    
31. 
    
32.     // 给定当前层的起始节点，遍历下一层的所有节点，并使用回调函数'callback'来处理。
    
33.     private void forEachNodeInNextLevel(Node levelStart, Consumer < Node > callback) {
    
34.         for (Node node = levelStart; node != null; node = node.next) {
    
35.             if (node.left != null) callback.accept(node.left);
    
36.             if (node.right != null) callback.accept(node.right);
    
37.         };
    
38.         // 一层的最后一个节点后面是null
    
39.         callback.accept(null);
    
40.     }

复制代码

我前两天刚被考到没有很快的得到O(1) space的解QAQ。。。然后就凉凉了orz 现在大概记一辈子吧。。。。