Interview Classic 150 Questions P114 Flatten Binary Tree to Linked List

---

Timeline

Timeline

2025-10-27

init

Non-recursive form of preorder traversal

---

Title:

P114 Flatten Binary Tree to Linked List

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-interview-150

Using non-recursive form of binary tree traversal

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}
pub struct Solution;

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {
        // Preorder traversal
        let mut stack = Vec::new();
        let mut vec = Vec::new();
        let mut p = root.clone();

        // Preorder traversal
        while let Some(node) = p {
            vec.push(node.clone());
            // Push the right child node onto the stack
            if let Some(right) = node.borrow().right.clone() {
                stack.push(right);
            }
            // Push the left child node onto the stack; if the left child is empty, pop the stack; otherwise p = Some(left)
            if let Some(left) = node.borrow().left.clone() {
                p = Some(left);
            } else {
                p = stack.pop();
            }
        }
        for i in 0..vec.len() {
            let node = vec[i].clone();
            node.borrow_mut().left = None;
            if i + 1 < vec.len() {
                node.borrow_mut().right = Some(vec[i + 1].clone());
            } else {
                node.borrow_mut().right = None;
            }
        }
    }
}

fn main() {
    println!("Hello, world!");
}

leetcode hot 100 rewrite

#include <vector>
#include <stack>
using std::stack;
using std::vector;

class Solution {
    public:
        void flatten(TreeNode *root)
        {
                if (root == nullptr)
                        return;
                int i, n;
                vector<TreeNode *> link;

                stack<TreeNode *> stk;
                TreeNode *p = root;

                while (p || !stk.empty()) {
                        if (p) {
                                link.push_back(p);
                                stk.push(p);
                                p = p->left;
                        } else {
                                p = stk.top();
                                stk.pop();
                                p = p->right;
                        }
                }
                n = link.size();
                for (i = 0; i < n - 1; i++) {
                        link[i]->right = link[i + 1];
                        link[i]->left = nullptr;
                }
                link[n - 1]->right = nullptr;
                link[n - 1]->left = nullptr;
        }
};

The in-place solution is a variant of Morris traversal. Morris traversal points the predecessor node’s right child to the current node; here, the predecessor node’s right child points to the current node’s right child.
This animation in the LeetCode solution is particularly helpful for understanding.

O(1) space complexity

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solutions/356853/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/?envType=study-plan-v2&envId=top-100-liked

struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode()
                : val(0)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x)
                : val(x)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x, TreeNode *left, TreeNode *right)
                : val(x)
                , left(left)
                , right(right)
        {
        }
};

class Solution {
    public:
        void flatten(TreeNode *root)
        {
                TreeNode *curr = root, *curr_left, *curr_left_rightest;

                while (curr) {
                        curr_left = curr->left;
                        if (curr_left) {
                                curr_left_rightest = curr_left;
                                while (curr_left_rightest->right != nullptr)
                                        curr_left_rightest = curr_left_rightest->right;

                                curr_left_rightest->right = curr->right;
                                curr->right = curr_left;
                                curr->left = nullptr;
                        }
                        curr = curr->right;
                }
        }
};