求救897. Increasing Order Search Tree，想了一晚上也没看懂的答案

就是最高vote的答案，具体如下：
public TreeNode increasingBST(TreeNode root) {
        return increasingBST(root, null);
    }

    public TreeNode increasingBST(TreeNode root, TreeNode tail) {
        if (root == null) return tail;
        TreeNode res = increasingBST(root.left, root);
        root.left = null;
        root.right = increasingBST(root.right, tail);
        return res;
    }

真的看不懂这几个递归的关系，有返回值感觉应该是divide&conquer， 但也不像一般的divide&conquer返回值对称的情况，这个函数的意义是每个子树的最左点（即head吗）？又像是用了tail节点来traverse记录需要连接的点,但是代码里也并没有.right=tail这样的代码， 请问是如何链接上的？
求大神解答以及提供这个代码的运行流程图或思考方法，不胜感激。

FightingBBY 发表于 2019-6-6 04:46
原谅小白，前面那个指针啊？ 通过那个语句连起来的？

就是 root.right = increasingBST(root.right, tail);
然后终止状态是  if (root == null) return tail;
这块可能挺难理解的（实际面试不太推荐写这么tricky的解法, 这是我之前写的代码 https://paste.ubuntu.com/p/7MpZVrQZcQ/ ， 虽然长了点，但很好理解）

这个答案挺有意思的，首先得明确知道increasingBST(TreeNode root, TreeNode tail) 干了什么，参数里面 root 是一个tree, tail是已完成的链，这个函数实现了把root转成一条链，然后再把tail这条链接上去，形成新的链并返回，具体操作如下：
1. 把root左儿子转成一个链，并把root接到这条链的后面
       TreeNode res = increasingBST(root.left, root); （不过此时第二个参数root并不是链，但你可以假设它是，因为在第二步会做, lazy update?）
2. 将 root左儿子清除，并将root右儿子转成链
       root.left = null;
       root.right = increasingBST(root.right, tail);
      
非常tricky的一个解法，不过代码挺短的~

337845818 发表于 2019-6-7 21:26
你想怎么定义都可以, 树是一种特殊的dag图, 解法就那么几种.
这题你不能理解的话, 大概你试试preorder t ...

醉了，这不是inorder traverse吗（左根右）？ 返回的就是最左节点（也是root右边该链接的那个点），只是当运行到root==null的时候分情况return应该链接的下一个点。前面大神解释清楚了。不知道怎么又来了preorder traverse...恐怕回复错了题目吧

zjck1995 发表于 2019-6-6 03:11
这个答案挺有意思的，首先得明确知道increasingBST(TreeNode root, TreeNode tail) 干了什么，参数里面 roo ...

谢谢大神，赶紧抓住再问问！！！
大概精神我也能领会一二，就像你说的一样，但是就是纠结在他是怎么把这个链串接上的，代码里并没有对tail做任何操作，比如tail.right或者tail.left啊

FightingBBY 发表于 2019-6-6 03:57
谢谢大神，赶紧抓住再问问！！！
大概精神我也能领会一二，就像你说的一样，但是就是纠结在他是怎么把这 ...

不需要对tail进行操作，tail这个参数表示指向一条链的头部，是已经处理好的，只需要把前面的指针指向这个tail就好了

zjck1995 发表于 2019-6-6 04:34
不需要对tail进行操作，tail这个参数表示指向一条链的头部，是已经处理好的，只需要把前面的指针指向这个 ...

原谅小白，前面那个指针啊？ 通过那个语句连起来的？

FightingBBY 发表于 2019-6-6 04:46
原谅小白，前面那个指针啊？ 通过那个语句连起来的？

嗯嗯我自己也按自己想法解答了，只是看到这个答案这么多vote就很好奇。其实可以不可以理解root.right = increasingBST(root.right, tail); 就是将根和右子树最左的节点连在一起。如果是叶子节点，则分为：
做叶子就返回自己的parent，右叶子返回自己parent 的parent？

FightingBBY 发表于 2019-6-6 07:02
嗯嗯我自己也按自己想法解答了，只是看到这个答案这么多vote就很好奇。其实可以不可以理解root.right = i ...

我其实没太看懂你的意思，不过vote高并不一定是最好的，这道题其实很简单，无非十几行的代码就可以表述得非常清楚，没必要为了极致优化代码行数而写成这样，也不需要纠结这个

本质上是in order visit, 递归, 不是d&c.
你不懂递归的话自然很难理解.
如果你不懂dfs bfs的话, 还是先看图题再考虑树题.

zjck1995 发表于 2019-6-6 15:02
我其实没太看懂你的意思，不过vote高并不一定是最好的，这道题其实很简单，无非十几行的代码就可以表述得 ...

好吧，我就是觉得如果我理解不了，肯定还是递归没有掌握到位