Bloomberg跪经 Mar 23

我怎么感觉把down替换成left，next替换成right，这就是一道pre order traversal 呢。不就是换了个variable 那么吗？

1peter 发表于 2016-3-25 11:58
我怎么感觉把down替换成left，next替换成right，这就是一道pre order traversal 呢。不就是换了个variable  ...

是的！精辟！

感觉确实就是：https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ 然后left变成了down，right变成了next。
public class FlattenDownTree{

        public void flatten (TreeNode root) {
            if (root.down!= null) {
              ListNode temp = root.next;
              root.next = root.down;
              ListNode nextRoot = root.next;

              root.down = null;

             while (root.next != null) {
                    root = root.next;
             }
             root.next = temp;

             flatten(nextRoot);

            }else {
             flatten (root.next);
            }
        }
}

估计 O(1) 就是每次 CustomLinkedNode node = head.down;
开个辅助接点，就叫O（1）
stack 要存O（h）

public void flatteNode(Node l) {
        if (l == null) {
            return;
        }
        flathelper(l);
    }
    public Node flathelper(Node root) {
        if (root == null) {
            return null;
        }
        if (root.next == null && root.down == null) {
            return root;
        }
        if (root.down == null) {
            return flathelper(root.next);
        }
        if (root.next == null) {
            root.next = root.down;
            root.down = null;
            return flathelper(root.next);
        }
        Node leftLast = flathelper(root.down);
        Node rightlast = flathelper(root.next);
        leftLast.next = root.next;
        root.next = root.down;
        root.down = null;
        return rightlast;
    }

感谢分享~ 请问这题复杂度是O(n)吗 0.0