LeetCode Problem:Flatten Binary Tree to Linked List

By | 2012 年 12 月 16 日

We can notice that in the flattened tree, each sub node is the successor node of it’s parent node in the pre-order of the original tree. So, we can do it in recursive manner, following the steps below:
1.if root is NULL return;
2.flatten the left sub tree of root, if there is left sub-tree;
3.flatten the right sub-tree of root, if has;
4.if root has no left sub-tree, then root is flattened already, just return;
5.we need to merge the left sub-tree with the right sub-tree, by concatenate the right sub-tree to the last node in left sub-tree.
5.1.find the last node in the left sub tree, as the left is flattened, this is easy.
5.2.concatenate the right sub-tree to this node’s right child.
5.3.move the left sub-tree to the right for root.
5.4.clear the left child of root.
6.done.

<br>
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6



Code:48ms to accept with large test set.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) return;
        //1.flat the left subtree
        if (root->left)
            flatten(root->left);
        //2.flatten the right subtree
        if (root->right)
            flatten(root->right);
        //3.if no left return
        if (NULL == root->left)
            return;
        //4.insert left sub tree between root and root->right
        //4.1.find the last node in left
        TreeNode ** ptn = & (root->left->right);
        while (*ptn)
            ptn = & ((*ptn)->right);
        //4.2.connect right sub tree after left sub tree
        *ptn = root->right;
        //4.3.move left sub tree to the root's right sub tree
        root->right = root->left;
        root->left = NULL;
        
    }
};



Code rewrite at 2013-2-20, non-recursive version

class Solution {
public:
    void flatten(TreeNode *root) {
        bool f = true;
        stack t;
        TreeNode *pre = NULL;
        if(root) {
            t.push(root);
        }
        
        while(t.size()) {
            TreeNode *cur = t.top();
            if(f) {
                if(cur->left && cur->left != pre) {
                    t.push(cur->left);
                } else {
                    f = false;
                }
            } else {
                if(cur->right && cur->right != pre) {
                    t.push(cur->right);
                    f = true;
                } else {
                    t.pop();
                    //at this time, the sub-tree of cur is flattened, so just flatten the cur
                    TreeNode *left = cur->left;
                    if(left) {
                        TreeNode *lastLeft = left;
                        while(lastLeft->right) {
                            lastLeft = lastLeft->right;
                        }
                        lastLeft->right = cur->right;
                        cur->right = left;
                        cur->left = NULL;
                    }
                }
            }
            pre = cur;
        }
    }
};

2 thoughts on “LeetCode Problem:Flatten Binary Tree to Linked List

  1. deju.zheng

    A much simpler solution.
    public class Solution {
    public void flatten(TreeNode root) {
    // Start typing your Java solution below
    // DO NOT write main() function
    preOrder(root, null);
    return;
    }

    public static TreeNode preOrder(TreeNode root, TreeNode prev) {
    if (root == null) return null;

    TreeNode leftNode = root.left;
    TreeNode rightNode = root.right;

    if (prev == null) {
    prev = root;
    } else {
    prev.left = null;
    prev.right = root;
    prev = root;
    }

    if (leftNode != null) {
    prev = preOrder(leftNode, prev);
    }
    if (rightNode != null) {
    prev = preOrder(rightNode, prev);
    }
    return prev;
    }
    }

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注