首页 > 数据结构 > 树形结构 > LeetCode-Flatten Binary Tree to Linked List[二叉树]
2014
11-19

LeetCode-Flatten Binary Tree to Linked List[二叉树]

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

click to show hints.

Hints:

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

标签: Tree Depth-first Search
分析

代码1

// LeetCode, Flatten Binary Tree to Linked List
// 递归版1,时间复杂度O(n),空间复杂度O(logn)
class Solution {
public:
    void flatten(TreeNode *root) {
        if (root == nullptr) return;  // 终止条件

        flatten(root->left);
        flatten(root->right);

        if (nullptr == root->left) return;

        // 三方合并,将左子树所形成的链表插入到root和root->right之间
        TreeNode *p = root->left;
        while(p->right) p = p->right; //寻找左链表最后一个节点
        p->right = root->right;
        root->right = root->left;
        root->left = nullptr;
    }
};

代码2

// LeetCode, Flatten Binary Tree to Linked List
// 递归版2
// @author 王顺达(http://weibo.com/u/1234984145)
// 时间复杂度O(n),空间复杂度O(logn)
class Solution {
public:
    void flatten(TreeNode *root) {
        flatten(root, NULL);
    }
private:
    // 把root所代表树变成链表后,tail跟在该链表后面
    TreeNode *flatten(TreeNode *root, TreeNode *tail) {
        if (NULL == root) return tail;

        root->right = flatten(root->left, flatten(root->right, tail));
        root->left = NULL;
        return root;
    }
};

代码3

// LeetCode, Flatten Binary Tree to Linked List
// 迭代版,时间复杂度O(n),空间复杂度O(logn)
class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return;

        stack<TreeNode*> s;
        s.push(root);

        while (!s.empty()) {
            auto p = s.top();
            s.pop();

            if (p->right)
                s.push(p->right);
            if (p->left)
                s.push(p->left);

            p->left = nullptr;
            if (!s.empty())
                p->right = s.top();
        }
    }
};

Java代码:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 

public class Solution {
    public void flatten(TreeNode root) {
       if(root == null){
            return;
        }
        
        if(root.left != null){
            TreeNode rightNode = root.right;
            TreeNode leftNode = root.left;
            root.left = null;
            root.right = leftNode;
            TreeNode p = leftNode;
            while(p.right != null){
                p = p.right;
            }
            p.right = rightNode;
        }
        flatten(root.right);
        
    }
    
    
}

  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish