Leetcode_114_Flatten Binary Tree to Linked List

[lihe]

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

算法思路：

方法一：

1. 前序遍历二叉树，将节点指针push进入vector；
2. 顺序遍历vector中的节点，将前面的节点的左指针置空，右指针与后面的节点相连。

该方法可以通过题目，但是不满足in-place的条件。

class Solution{
public:
    void flatten(TreeNode* root){
        std::vector<TreeNode*> node_vec;
        preorder(root, node_vec);
        for(int i = 1; i < node_vec.size(); i++){
            node_vec[i - 1] -> left = NULL;
            node_vec[i - 1] -> right = node_vec[i];
        }
    }

private:
    void preorder(TreeNode* node, std::vector<TreeNode*> &node_vec){
        if(!node){
            return;
        }
        node_vec.push_back(node);
        preorder(node -> left, node_vec);
        preorder(node -> right, node_vec);
    }
};

方法二：

1. 从下往上，将每个节点的右子树放到左子树的最右节点；
2. 将左子树放到右子树，并将左子树置空。

class Solution{
public:
    void flatten(TreeNode* root){
        TreeNode* last = NULL;
        preorder(root, last);
    }

private:
    void preorder(TreeNode* node, TreeNode* &last){
        if(!node){
            return;
        }
        if(!node -> left && !node -> right){
            last = node;
            return;
        }
        TreeNode* left = node -> left;
        TreeNode* right = node -> right;
        TreeNode* left_last = NULL;
        TreeNode* right_last = NULL;
        if(left){
            preorder(left, left_last);
            node -> left = NULL;
            node -> right = left;
            last = left_last;
        }
        if(right){
            preorder(right, right_last);
            if(left_last){
                left_last -> right = right;
            }
            last = right_last;
        }
    }
};