翻转二叉树

描述

在本节课中，你的任务是反转给定的二叉树 T。

让我们看一个示例：

1fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
2    root
3}

解法

我们可以使用 深度优先搜索（DFS） 来解决这个问题。

空树的反转仍然是空树。要反转以 root 为根、左右子树分别为 left 和 right 的二叉树 T，我们保持根节点不变，仅反转左右子树。

让我们回顾以下实现：

1fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
2    match &root {
3        Some(node) => {
4            let left = invert_tree(node.borrow().left.clone());
5            let right = invert_tree(node.borrow().right.clone());
6            node.borrow_mut().left = right;
7            node.borrow_mut().right = left;
8        },
9        None => {}
10    };
11    root
12}

1fn main() {
2    let mut root = TreeNode::new(1);
3    root.left = Some(Rc::new(RefCell::new(TreeNode::new(2))));
4    root.right = Some(Rc::new(RefCell::new(TreeNode::new(3))));
5    root.left.clone().unwrap().borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(4))));
6    root.left.clone().unwrap().borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(5))));
7    root.right.clone().unwrap().borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(6))));
8    root.right.clone().unwrap().borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(7))));
9
10    let res = invert_tree(Some(Rc::new(RefCell::new(root))));
11    let res1 = level_order(res);
12    println!("{:?}", res1);
13}

复杂度分析

时间复杂度

时间复杂度为 $O(N)$，其中 N 是树中节点的数量，因为我们需要访问每个节点一次。

空间复杂度

空间复杂度为 $O(N)$，其中 N 是树中节点的数量。最坏情况下，树的高度等于 N（例如倾斜树），因此递归调用栈的最大深度为 O(N)。