从114. Flatten Binary Tree to Linked List展开兼谈Tree的传值问题

114. Flatten Binary Tree to Linked List

Tree的递归/DFS博大精深，出题千变万化，但是有一类解法可以攻破很多这种问题，而且适用于几乎所有Tree的Recursion题目，请大家多多加米，如何加米？ 我这个楼的下方有“收藏”“评分”“淘贴”，请选择“评分”加米，多谢！
如果你看看我的总结帖子，会发现我总结的都是方法，是每类题的解法，而不是每个题的具体解法，原创不易。

需要从下层返回什么，我就返回什么
如果要返回多个值
如果类型相同，则用一个array即可；
如果类型不同，建一个class把所有值作为field放进去。
对于此题，需要链表的头和尾，这样才能把2个链表接上，所以用一个array即可。但要注意的是base case不要写错：就是只有一个节点时，头和尾均为此节点，否则如果尾是null，那就是null接下一个链表的头了，完全错误！！！

同样的方法轻松解决426题，而且特别清晰易懂，可以和面试官讲清楚，像Leetcode高票答案那种，第一很难理解，第二很不一定能和面试官解释清楚。
还有同学问我一个问题，他也是下面写法，但是他把一个res 的array作为参数传进函数里，问我为什么不对？这里简单说一下Java的传参，Java只有pass by value，如果是primitive type比如int 啊 a= 5，则传入的是这个a 的copy，等于是再copy出一个数5传入函数中，函数执行完根本不改变a的值。而如果是Object，则传入的是Object的地址的copy，所以在此地址上作出的内容改变都改变了Object的值，所以不能传一个array进去而且返回的还是这个array！！！

1. 
   
2. public TreeNode flatten(TreeNode root) {
   
3.    if (root == null || (root.left == null && root.right == null)) {
   
4.      return root;
   
5.    }
   
6.       
   
7.    helper(root);
   
8.    return root;
   
9. }
   
10. 
    
11. private TreeNode[] helper(TreeNode node) {
    
12.    TreeNode[] res = new TreeNode[2];
    
13.    if (node == null) {
    
14.      return res;
    
15.    }
    
16. 
    
17.    if (node.left == null && node.right == null) {
    
18.      res[0] = node;
    
19.      res[1] = node;
    
20.      return res;
    
21.    }
    
22. 
    
23.    TreeNode[] right = helper(node.right);
    
24.    TreeNode[] left = helper(node.left);
    
25.    if (node.left == null) {
    
26.      res[0] = node;
    
27.      res[1] = right[1];
    
28.      return res;
    
29.    } else if (node.right == null) {
    
30.      res[0] = node;
    
31.      res[1] = left[1];
    
32.      node.right = left[0];
    
33.      node.left = null;
    
34.      return res;
    
35.    } else {
    
36.      node.right = left[0];
    
37.      left[1].right = right[0];
    
38.      node.left = null;
    
39.      res[0] = node;
    
40.      res[1] = right[1];
    
41.      return res;
    
42.    }
    
43. }
    

复制代码

426. Convert Binary Search Tree to Sorted Doubly Linked List

1. public Node treeToDoublyList(Node root) {
   
2.         Node[] r = flatten(root);
   
3.         if (r[0] != null) {
   
4.             r[0].left = r[1];
   
5.             r[1].right = r[0];
   
6.         }
   
7.         return r[0];
   
8.     }
   
9.    
   
10.     private Node[] flatten(Node root) {
    
11.         if (root == null) return new Node[] {null, null};
    
12.         Node[] left = flatten(root.left);
    
13.         Node[] right = flatten(root.right);
    
14.         Node first = root;
    
15.         if (left[1] != null) {
    
16.             left[1].right = root;
    
17.             root.left = left[1];
    
18.             first = left[0];
    
19.         }
    
20.         Node last = root;
    
21.         if (right[0] != null) {
    
22.             root.right = right[0];
    
23.             right[0].left = root;
    
24.             last = right[1];
    
25.         }
    
26.         return new Node[] {first, last};
    
27.     }

复制代码

补充内容 (2021-05-19 12:18 +8:00):
第一题第一个函数内加一行TreeNode[] res = helper(root); return res[0]