面试经典150题 P114 二叉树展开为链表

---

时间轴

时间轴

2025-10-27

init

先序遍历的非递归形式

---

题目：

P114 二叉树展开为链表

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

使用二叉树遍历的非递归形式

// 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>>>) {
        // 先序遍历
        let mut stack = Vec::new();
        let mut vec = Vec::new();
        let mut p = root.clone();

        // 先序遍历
        while let Some(node) = p {
            vec.push(node.clone());
            // 把右子节点压入栈中
            if let Some(right) = node.borrow().right.clone() {
                stack.push(right);
            }
            // 左子节点压入栈中，如果左子节点为空则退栈，否则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;
        }
};

原地解法是 morris 遍历的一种变体形式，莫里斯遍历是将前驱结点的右子结点指向当前结点，这里是前驱结点的右子结点指向当前结点的右子结点。
leetcode 题解的这个动画特别方便理解

O(1) 空间复杂度

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;
                }
        }
};