Tree2List

Way of thinking

window by window 1) 区间对应区间 2) 进出区间的时候，应该做的一些操作

这类题一直是我的难点。主要是观察不出来树的结构是怎么变化的。

Flatten Binary Tree to LinkedList

Problem Description

这个相对比较容易观察。

为什么一开始错了?

没有注意到以下所有的分析都是基于左子树不是null，左子树也不是null的情况。

For each root node :

Step 1: flatten left subtree to a linkedlist. get head,tail of transformed linkedlist.

Step 2: flatten right subtree to a linkedlist, get head, tail of transformed linkedlist.

Step 3 : root.next = leftList.head; leftList.tail = rightList.head;

Step 4: root is new head of list, and right.tail is tail of return list.

Base case: (分析错了).

only one node, return itself as head and tail.

    public void flatten (TreeNode root) {
        if (root == null) {
            return;
        }
        helper(root);
        return root;
    }
    //return type: [head, tail] 
    //invariant : linkedlist constructed from tree rooted at root
    TreeNode[] helper (TreeNode root) {
        if (root == null) {
            return new TreeNode[2];
        }
        if (root.left == null && root.right == null) {
            return new TreeNode[]{root,root};
        }
        TreeNode[] leftList = helper(root.left);
        TreeNode[] rightList = helper(root.right);
        //forgot at first
        root.left = null;
        //case 1 : left is null
        if (leftList[0] == null) {
           root.right  = rightList[0];
           return new TreeNode[]{root,rightList[1]};
        }
        //case 2 : left is not null
        else {
          root.right = leftList[0];
          leftList[1].right = rightList[0];
          //forgot at first.
          if (rightList[0] == null) {
                return new TreeNode[] {root,leftList[1]};
          }
          return new TreeNode[] {root, rightList[1]};
        }
    }

Convert Tree to Circular linkedlist

assume we have utility function

a) join() - connect two list nodes

b) append() - append two lists

    public void join(Node a, Node b) {
        a.right = b;
        b.left = a;
    }

    Node append(Node a, Node b) {
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }
        Node aLast = a.left;
        Node bLast = b.left;
        join(aLast,b);
        join(bLast,a);
    }

Divide and conquer. 1) Convert left subtree to circular linkedlist , return left root. 2) Convert right subtree to circular linkedlist, return right root.