Massive Algorithms: LeetCode

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
Given a binary tree, flatten it to a linked list in-place.

For example,given

The flattened tree should look like:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
Recursive Version:

X. https://discuss.leetcode.com/topic/11444/my-short-post-order-traversal-java-solution-for-share
I would rename "prev" with "nxt" for the purpose of clarification

private TreeNode prev = null;

public void flatten(TreeNode root) {
    if (root == null)
        return;
    flatten(root.right);
    flatten(root.left);
    root.right = prev;
    root.left = null;
    prev = root;
}

X. http://bangbingsyb.blogspot.com/2014/11/leetcode-flatten-binary-tree-to-linked.html
假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了：

1
/ \
2 5
\ \
3 6 <- rightTail
\
4 <- leftTail

如何将root、T(root->left)、T(root->right) flatten成一整个linked list？显而易见：

temp = root->right
root->right = root->left
root->left = NULL
leftTail->right = temp

这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。

需注意几个细节
ln 11：只有当左子树存在时才将它插入右子树中
ln 18-20：返回尾部元素时，需要特殊处理 (1) 有右子树的情况，(2) 无右子树但有左子树的情况，(3)左右子树均不存在的情况。

TreeNode flatten(TreeNode root) {

if (root == null)

return null;

TreeNode leftTail = flatten(root.left);

TreeNode rightTail = flatten(root.right);

if (root.left != null) {

TreeNode temp = root.right;

root.right = root.left;

root.left = null;

leftTail.right = temp;

}

if (rightTail != null)

return rightTail;

if (leftTail != null)

return leftTail;

return root;

}

X. Pre-order
http://fisherlei.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html

TreeNode pre;

void flatten(TreeNode root) {

if (root == null)

return;

TreeNode right = root.right;

if (pre != null) {

pre.left = null;

pre.right = root;

}

pre = root;

flatten(root.left);

flatten(right);

}

X. http://bangbingsyb.blogspot.com/2014/11/leetcode-flatten-binary-tree-to-linked.html

从题目的例子马上发现其实就是preorder transverse整个tree，然后根据这个访问顺序，后访问到的节点成为先访问到的节点的右子节点。那么最不动脑的方法就是preorder transverse的时候把整个节点序列保存在一个vector中。最后再依次连起来。这个解法的空间复杂度包括了递归深度O(log n)和vector的空间O(n)，所以总的空间复杂度是O(n)。

    void flatten(TreeNode *root) {
        if(!root) return;
        vector<TreeNode*> allNodes;
        preorder(root, allNodes);
        int n = allNodes.size();
        for(int i=0; i<n-1; i++) {
            allNodes[i]->left = NULL;
            allNodes[i]->right = allNodes[i+1];
        }
        allNodes[n-1]->left = allNodes[n-1]->right = NULL;
    }
    
    void preorder(TreeNode *root, vector<TreeNode*> &allNodes) {
        if(!root) return;
        allNodes.push_back(root);
        preorder(root->left, allNodes);
        preorder(root->right, allNodes);
    }

X. Noe efficient:
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/36987/Straightforward-Java-Solution

public void flatten(TreeNode root) {
        if (root == null) return;
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        
        root.left = null;
        
        flatten(left);
        flatten(right);
        
        root.right = left;
        TreeNode cur = root;
        while (cur.right != null) cur = cur.right;
        cur.right = right;
    }

This solution is based on recursion. We simply flatten left and right subtree and paste each sublist to the right child of the root. (don't forget to set left child to null)

From http://fisherlei.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html

void flatten(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root == NULL)
return;
ConvertToLink(root);
}
TreeNode* ConvertToLink(TreeNode* node)
{
if(node->left == NULL && node->right == NULL)
return node;
TreeNode* rHead = NULL;
if(node->right != NULL)
rHead = ConvertToLink(node->right);
TreeNode* p = node;
if(node->left!=NULL)
{
TreeNode* lHead = ConvertToLink(node->left);
node->right = lHead;
lHead->left = NULL;
node->left = NULL;
while(p->right!=NULL)
p = p->right;
}
if(rHead != NULL)
{
p->right = rHead;
rHead->left = NULL;
}
return node;

}
[已犯错误]
1. Line 13~14
刚开始的时候，首先flatten左树，然后处理右树。但是这样会导致处理右树的时候，节点的值已经在处理树的时候被破坏了。比如树为{1,2,3}，
1
/ \
2 3
如果先处理左树的话，当执行node->right = lhead的时候，右节点就已经被破坏了，node->right指向了2，而不是3。
1
\
2 (3)
当然，也可以用一个变量在处理左树前，保存右树地址。但是没必要，先处理右树就好了。
2. Line 22~23
该循环是用于将p指针遍历到左树链表的最右节点。第一版时，这个循环是放在if语句以外，这就导致了，不必要的迭代了。比如当输入为{1,#,2}时，这个while循环会导致p指针遍历到右子树的最右节点，这显然是错的。
3. Line 20, 28
不要忘了清空每一个指针，在新的链表中，左指针没必要保留
from http://www.darrensunny.me/leetcode-flatten-binary-tree-to-linked-list/

private TreeNode recursiveFlatten(TreeNode t) {

        if (t == null)      // Empty tree

            return null;

        // Recursively flatten its left and right subtrees

        TreeNode leftLeaf = recursiveFlatten(t.left);

        TreeNode rightLeaf = recursiveFlatten(t.right);

        if (leftLeaf == null && rightLeaf == null)    // The tree is a leaf itself

            return t;

        if (leftLeaf == null)    // Has only right subtree; already flattened

            return rightLeaf;

        if (rightLeaf == null) { // Has only left subtree; make it right

            t.right = t.left;

            t.left = null;

            return leftLeaf;

}

        // Has both left and right subtrees

        // Put the left subtree in between the root and the right subtree

        TreeNode temp = t.right;

        t.right = t.left;

        t.left = null;

        leftLeaf.right = temp;

        return rightLeaf;

}

Iterative Version:
Use stack from http://www.programcreek.com/2013/01/leetcode-flatten-binary-tree-to-linked-list/
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/36991/Accepted-simple-Java-solution-iterative
Go down through the left, when right is not null, push right to stack.

public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
 
        while(p != null || !stack.empty()){
 
            if(p.right != null){
                stack.push(p.right);
            }
 
            if(p.left != null){
                p.right = p.left;
                p.left = null;
            }else if(!stack.empty()){
                TreeNode temp = stack.pop();
                p.right=temp;
            }
 
            p = p.right;
        }
    }

Also read http://blog.csdn.net/perfect8886/article/details/20000083
https://discuss.leetcode.com/topic/5783/accepted-simple-java-solution-iterative

it is DFS so u need a stack. Dont forget to set the left child to null, or u'll get TLE. (tricky!)

   public void flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stk = new Stack<TreeNode>();
        stk.push(root);
        while (!stk.isEmpty()){
            TreeNode curr = stk.pop();
            if (curr.right!=null)  
                 stk.push(curr.right);
            if (curr.left!=null)  
                 stk.push(curr.left);
            if (!stk.isEmpty()) 
                 curr.right = stk.peek();
            curr.left = null;  // dont forget this!! 
        }
    }

O(N^2)
https://discuss.leetcode.com/topic/9936/straightforward-java-solution

public void flatten(TreeNode root) {
        if (root == null) return;
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        
        root.left = null;
        
        flatten(left);
        flatten(right);
        
        root.right = left;
        TreeNode cur = root;
        while (cur.right != null) cur = cur.right;
        cur.right = right;
    }

This solution is based on recursion. We simply flatten left and right subtree and paste each sublist to the right child of the root. (don't forget to set left child to null)

X. Follow up
http://fisherlei.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html
Update 08/25/2014 being asked this question today. But the interviewer asked for an in-order flatten.
Review previous solution. Actually, I made it too complicate. If travel this tree in pre-order, from the hint, it is easy to construct the linked list.

1:       void flatten(TreeNode *root) {  
2:            if(root == NULL) return;  
3:            TreeNode* right = root->right;  
4:            if(lastVisitedNode != NULL)  
5:            {  
6:                 lastVisitedNode->left = NULL;  
7:                 lastVisitedNode->right = root;  
8:            }  
9:            lastVisitedNode = root;  
10:            flatten(root->left);  
11:            flatten(right);  
12:       }

pre-order is simple because the root always is the head of flatten list. But if flatten the tree with in-order sequence, need extra parameter to track the head and tail of each flattened sun-tree.
For example, below binary tree.

If we flatten it with in-order, the process should like below. And here I use the left pointer of head node to track the tail node.

1:  TreeNode* flatten(TreeNode *root) {  
2:       if (root == NULL) return NULL;  
3:       TreeNode* rightTree = root->right;  
4:       TreeNode* newHead = root;  
5:       TreeNode* leftList = flatten(root->left);  
6:       if (leftList != NULL)  
7:       {  
8:            newHead = leftList;  
9:            TreeNode* tail = leftList->left;  
10:            tail->right = root;  
11:            root->left = tail;  
12:            leftList->left = root;  
13:       }  
14:       TreeNode* rightList = flatten(rightTree);  
15:       if (rightList != NULL)  
16:       {  
17:            root->right = rightList;  
18:            newHead->left = rightList->left;  
19:            rightList->left = root;  
20:       }  
21:       return newHead;  
22:  }

Read full article from LeetCode - Flatten Binary Tree to Linked List | Darren's Blog

LeetCode - Flatten Binary Tree to Linked List

Labels

Popular Posts