跳至主要內容

145, 二叉树的后序遍历

Mike大约 3 分钟binary treeeasystackbinary treedepth first search

一、题目描述

给你一棵二叉树的根节点root,返回其节点值的后序遍历

示例 1
3 nodes
输入: root = [1, null, 2, 3]
输出: [3, 2, 1]

示例 2
输入: root = []
输出: []

示例 3
输入: root = [1]
输出: [1]

提示

  • 树中节点的数目在范围[0, 100]
  • -100 <= Node.val <= 100

进阶
递归算法很简单,你可以通过迭代算法完成吗?

相关主题

  • 深度优先搜索
  • 二叉树

二、题解

#[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,
        }
    }
}

方法 1: 递归

pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut res = vec![];
    const RECURSION_IMPL: fn(root: Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) =
        |root, res| match root {
            None => {}
            Some(curr) => {
                RECURSION_IMPL(curr.borrow_mut().left.take(), res);
                RECURSION_IMPL(curr.borrow_mut().right.take(), res);
                res.push(curr.borrow().val);
            }
        };

    RECURSION_IMPL(root, &mut res);

    res
}

方法 2: 迭代

pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    //Self::iteration_impl_1(root)
    //Self::iteration_impl_2(root)
    //Self::iteration_impl_3(root)
    Self::iteration_impl_4(root)
}

fn iteration_impl_1(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut res = vec![];

    if let Some(root) = root {
        let mut stack = vec![root];

        while let Some(curr) = stack.pop() {
            res.push(curr.borrow().val); // Root
            if let Some(left) = curr.borrow_mut().left.take() {
                stack.push(left); // Left
            }
            if let Some(right) = curr.borrow_mut().right.take() {
                stack.push(right); // Right
            }
        }
    }
    
    res.reverse(); // NRL -> LRN
    res
}

fn iteration_impl_2(mut root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut res = vec![];
    let mut stack = vec![];
    let mut last_visited = None;

    while root.is_some() || !stack.is_empty() {
        while let Some(curr) = root {
            root = curr.borrow_mut().left.take();
            stack.push(curr);
        }

        if let Some(curr) = stack.pop() {
            let right = curr.borrow_mut().right.take();
            if right.is_some() && !right.eq(&last_visited) {
                root = right;
                stack.push(curr);
            } else {
                res.push(curr.borrow().val);
                last_visited = right;
            }
        }
    }

    res
}

fn iteration_impl_3(mut root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut res = vec![];
    let mut stack = vec![];
    let mut last_visited = None;

    while root.is_some() || !stack.is_empty() {
        match root {
            Some(curr) => {
                root = curr.borrow_mut().left.take();
                stack.push(curr);
            }
            None => {
                if let Some(curr) = stack.pop() {
                    let right = curr.borrow_mut().right.take();
                    if right.is_some() && !right.eq(&last_visited) {
                        root = right;
                        stack.push(curr);
                    } else {
                        res.push(curr.borrow().val);
                        last_visited = right;
                    }
                }
            }
        }
    }

    res
}

fn iteration_impl_4(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut res = vec![];

    if let Some(root) = root {
        let mut stack = vec![Ok(root)];

        while let Some(curr) = stack.pop() {
            match curr {
                Ok(node) => {
                    stack.push(Err(node.borrow().val));
                    if let Some(right) = node.borrow_mut().right.take() {
                        stack.push(Ok(right));
                    }
                    if let Some(left) = node.borrow_mut().left.take() {
                        stack.push(Ok(left));
                    }
                }
                Err(val) => {
                    res.push(val);
                }
            }
        }
    }

    res
}