114. Flatten Binary Tree to Linked List

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/

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

Thoughts

按照pre-order顺序依次把所有结点压成linked list，right作为next指针。pre-order遍历并把root->left和right存下来做为下次遍历的起点，global cur记录上次遍历到的点，在它后面插入当前结点并更新cur。

Code

/*
 * @lc app=leetcode id=114 lang=cpp
 *
 * [114] Flatten Binary Tree to Linked List
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
       stack<TreeNode*> s;
       s.push(root);
       TreeNode *last = nullptr;
       while (!s.empty()) {
           auto t = s.top(); s.pop();
           if (t == nullptr) continue;
           s.push(t->right);
           s.push(t->left);
           if (last != nullptr) {
               last->left = nullptr;
               last->right = t;
           }
           last = t;
       } 
    }
};
// @lc code=end

/*
 * @lc app=leetcode id=114 lang=cpp
 *
 * [114] Flatten Binary Tree to Linked List
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *cur;
    void flatten(TreeNode* root) {
        if (root == nullptr) return;
        const auto left = root->left, right = root->right;
        root->left = nullptr;
        if (cur != nullptr) cur->right = root;
        cur = root;
        flatten(left);
        flatten(right);
    }
};
// @lc code=end

Analysis

Errors:

1. TreeNode iter = node; 初始化错误。不是当前结点的最右，而是左子树的最右。

时间复杂度O(n)

Ver.2

做一次pre-order traversal并把当前节点的左节点清空, 右节点连上pre-order的下一个(stack.peek()).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
            if (!stack.isEmpty()) {
                node.right = stack.peek();
            }
                node.left = null;
        }
    }
}