114. Flatten Binary Tree to Linked List

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

Question

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The "linked list" should be in the same order as a pre-order traversal of the binary tree.

初想法

这题基于114，就可以很容易的做出来。

值得注意的是直接node会更容易去遍历构造链表。

pub fn flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {
    if root.is_none() {
        return;
    }
    fn preorder_traversal_traverse(
        root: &mut Option<Rc<RefCell<TreeNode>>>,
    ) -> Vec<Rc<RefCell<TreeNode>>> {
        let mut ret = vec![];
        let mut stack = vec![root.clone()];
        while let Some(node) = stack.pop() {
            if let Some(node) = node {
                ret.push(node.clone());
                stack.push(node.borrow_mut().right.take());
                stack.push(node.borrow_mut().left.take());
            }
        }
        ret
    }
    let mut list = preorder_traversal_traverse(root);
    list.reverse();
    while let Some(node) = list.pop() {
        if list.len() != 0 {
            node.borrow_mut().right = Some(list.get(list.len() - 1).unwrap().clone());
        }
    }
}

总结

注意熟练掌握各种基础遍历，对于这种题目就会得心应手。