跳至主要內容

101, 对称二叉树

Mike大约 2 分钟binary treeeasybinary treedepth first searchbreadth first search

一、题目描述

给你一个二叉树的根节点root,检查它是否轴对称。

示例 1
symmetric_tree
输入: root = [1, 2, 2, 3, 4, 4, 3]
输出: true

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

提示

  • 树中节点数目在范围[1, 1000]
  • -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 is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    if let Some(root) = root {
        let mut l_r_root = root.borrow_mut().left.take();
        let mut r_l_root = root.borrow_mut().right.take();
        let mut l_r_stack = vec![];
        let mut r_l_stack = vec![];

        while l_r_root.is_some()
            || !l_r_stack.is_empty()
            || r_l_root.is_some()
            || !r_l_stack.is_empty()
        {
            match (l_r_root, r_l_root) {
                (Some(l_r_node), Some(r_l_node)) => {
                    if l_r_node.borrow().val != r_l_node.borrow().val {
                        return false;
                    }
                    l_r_root = l_r_node.borrow_mut().left.take();
                    l_r_stack.push(l_r_node);
                    r_l_root = r_l_node.borrow_mut().right.take();
                    r_l_stack.push(r_l_node);
                }
                (None, None) => match (l_r_stack.pop(), r_l_stack.pop()) {
                    (Some(l_r_node), Some(r_l_node)) => {
                        l_r_root = l_r_node.borrow_mut().right.take();
                        r_l_root = r_l_node.borrow_mut().left.take();
                    }
                    (_, _) => return false,
                },
                (_, _) => return false,
            }
        }
    }

    true
}

方法 2: 广度优先搜索

pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    //Self::bfs_recur(root)
    Self::bfs_iter(root)
}

///
/// 广度优先搜索 - 递归
///
fn bfs_recur(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    if let Some(root) = root {
        const HELPER: fn(Option<Rc<RefCell<TreeNode>>>, Option<Rc<RefCell<TreeNode>>>) -> bool =
            |left, right| match (left, right) {
                (Some(left), Some(right)) => {
                    left.borrow().val == right.borrow().val
                        && HELPER(left.borrow().left.clone(), right.borrow().right.clone())
                        && HELPER(left.borrow().right.clone(), right.borrow().left.clone())
                }
                (None, None) => true,
                (_, _) => false,
            };

        HELPER(root.borrow().left.clone(), root.borrow().right.clone())

    } else {

        true
    }
}

///
/// 广度优先搜索 - 迭代
///
fn bfs_iter(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    if let Some(root) = root {
        let mut queue = VecDeque::new();
        queue.push_back(root.borrow_mut().left.take());
        queue.push_back(root.borrow_mut().right.take());

        while !queue.is_empty() {
            match (queue.pop_front(), queue.pop_front()) {
                (Some(left), Some(right)) => match (left, right) {
                    (Some(left), Some(right)) => {
                        if left.borrow().val != right.borrow().val {
                            return false;
                        }
                        queue.push_back(left.borrow_mut().left.take());
                        queue.push_back(right.borrow_mut().right.take());
                        queue.push_back(left.borrow_mut().right.take());
                        queue.push_back(right.borrow_mut().left.take());
                    }
                    (None, None) => {}
                    (_, _) => return false,
                },
                (_, _) => return false,
            }
        }
    }

    true
}