用Rust🦀写算法-二叉树篇之二

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

invert1-tree.jpg

1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

invert2-tree.jpg

1
2
输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

1
2
输入：root = []
输出：[]

提示：

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

💡 思路：
本质上还是二叉树的遍历：

  1. 递归实现，每个节点递归处理左右子节点
  2. 迭代法深度优先（栈）实现
  3. 迭代法广度优先（层序遍历，队列）实现

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        match root {
            None => None,
            Some(root) => {
                let mut node = root.borrow_mut();
                let left = node.left.take();
                let right = node.right.take();
                
								// 后序遍历，先递归处理左右子树，再返回到这里处理本节点
                node.left = Self::invert_tree(right);
                node.right = Self::invert_tree(left);

                Some(root.clone())
            }
        }
    }
}

代码（思路二）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut stack = vec![root.clone()];
        while !stack.is_empty() {
            if let Some(node) = stack.pop().unwrap() {
                let (left, right) = (node.borrow().left.clone(), node.borrow().right.clone());
                stack.push(right.clone());
                stack.push(left.clone());
                // 前序遍历 先处理本节点，下次循环处理左右子节点
                node.borrow_mut().left = right;
                node.borrow_mut().right = left;
            }
        }
        root
    }
}

代码（思路三）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let root = match root {
            Some(r) => r,
            None => return None,
        };

        let mut queue = VecDeque::new();
        queue.push_back(Rc::clone(&root));
				
				// 这里没有使用 queue的大小进行for循环遍历，因为在该题中不需要分辨层数
        while let Some(node) = queue.pop_front() { 
            // 交换当前节点的左右子树
            let (left, right) = (node.borrow().left.clone(), node.borrow().right.clone());
            let mut node_ref = node.borrow_mut();
            node_ref.left = right;
            node_ref.right = left;

            // 将非空子节点加入队列
            if let Some(left) = &node_ref.left {
                queue.push_back(Rc::clone(left));
            }
            if let Some(right) = &node_ref.right {
                queue.push_back(Rc::clone(right));
            }
        }

        Some(root)
    }
}

101. 对称二叉树

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

示例 1：

1698026966-JDYPDU-image.png

1
2
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

1698027008-nPFLbM-image.png

1
2
输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

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

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

💡 思路：

  1. 递归法：
    a. 基本思想：比较左子树和右子树是否互为镜像
    b. 递归条件：
    1. 两个节点都为空 → 对称
    2. 一个为空一个不为空 → 不对称
    3. 两个节点值不相等 → 不对称
    4. 递归检查：左子树的左子树与右子树的右子树 && 左子树的右子树与右子树的左子树
  2. 迭代法：
    a. 使用队列：将需要比较的节点成对放入队列
    b. 比较过程：
    1. 每次从队列中取出两个节点比较
    2. 将左节点的左子节点与右节点的右子节点一起入队
    3. 将左节点的右子节点与右节点的左子节点一起入队

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        match root {
            None => true,
            Some(node) => {
                let node = node.borrow();
                Self::recursion(&node.left, &node.right)
            }
        }
    }

    fn recursion(
        left: &Option<Rc<RefCell<TreeNode>>>,
        right: &Option<Rc<RefCell<TreeNode>>>
    ) -> bool {
        match (left, right) {
            (None, None) => true,
            (Some(left), Some(right)) => {
                let l = left.borrow();
                let r = right.borrow();
                l.val == r.val &&
                    Self::recursion(&l.left, &r.right) &&
                    Self::recursion(&l.right, &r.left)
            }
            _ => false,
        }
    }
}

代码（思路二）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        let root = match root {
            Some(r) => r,
            None => return true,
        };

        let root = root.borrow();
        // 这里没有使用队列 因为我们要的只是两两比对，顺序并不影响结果
        let mut stack = vec![(root.left.clone(), root.right.clone())];

        while let Some((left, right)) = stack.pop() {
            match (left, right) {
                (None, None) => continue,
                (Some(l), Some(r)) => {
                    let l = l.borrow();
                    let r = r.borrow();
                    if l.val != r.val {
                        return false;
                    }
                    stack.push((l.left.clone(), r.right.clone()));
                    stack.push((l.right.clone(), r.left.clone()));
                }
                _ => return false,
            }
        }

        true
    }
}

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~2^h 个节点。

示例 1：

complete.jpg

1
2
输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

1
2
输入：root = []
输出：0

示例 3：

1
2
输入：root = [1]
输出：1

提示：

  • 树中节点的数目范围是[0, 5 * 10^4]
  • 0 <= Node.val <= 5 * 10^4
  • 题目数据保证输入的树是 完全二叉树

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

💡 思路：

  1. 递归法计数
  2. 迭代法（层序遍历）计数

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::count_nodes_ref(&root)
    }

    fn count_nodes_ref(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if let Some(r) = root {
            let node = r.borrow();
            // 左边节点个数 + 右边节点个数 + 1（本身）
            1 + Self::count_nodes_ref(&node.left) + Self::count_nodes_ref(&node.right)
        } else {
            0
        }
    }
}

代码（思路二）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;

impl Solution {
    pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let Some(root_node) = root else { return 0 };

        let mut queue = VecDeque::new();
        queue.push_back(root_node);
        let mut count = 0;

        while let Some(node) = queue.pop_front() {
            count += 1;
            let node_ref = node.borrow();

            if let Some(left) = node_ref.left.as_ref() {
                queue.push_back(left.clone());
            }
            if let Some(right) = node_ref.right.as_ref() {
                queue.push_back(right.clone());
            }
        }

        count
    }
}

进阶（递归解法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if let Some(node) = root {
            let left_depth = Self::compute_depth(node.borrow().left.clone());
            let right_depth = Self::compute_depth(node.borrow().right.clone());

            if left_depth == right_depth {
                // 左子树是满二叉树
                (1 << left_depth) + Self::count_nodes(node.borrow().right.clone())
            } else {
                // 右子树是满二叉树
                (1 << right_depth) + Self::count_nodes(node.borrow().left.clone())
            }
        } else {
            0
        }
    }

    fn compute_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut depth = 0;
        let mut current = root;

        while let Some(node) = current {
            depth += 1;
            current = node.borrow().left.clone();
        }

        depth
    }
}

110. 平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树

示例 1：

balance_1.jpg

1
2
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

balance_2.jpg

1
2
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

1
2
输入：root = []
输出：true

提示：

  • 树中的节点数在范围 [0, 5000] 内
  • -10^4 <= Node.val <= 10^4

💡 思路：
平衡二叉树是指对于二叉树中的每一个节点，其左子树和右子树的高度差不超过1。这意味着我们需要：

  1. 计算每个节点的左右子树高度
  2. 检查它们的高度差是否≤1
  3. 递归检查所有子树是否也满足这个条件

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
use std::rc::Rc;
use std::cell::RefCell;
use std::cmp;
impl Solution {
    pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        // 使用Result类型来同时传递高度和平衡信息
        Self::check_balanced(&root).is_ok()
    }

    // 返回Result类型：
    // Ok(height) 表示子树平衡且返回高度
    // Err(()) 表示子树不平衡
    fn check_balanced(root: &Option<Rc<RefCell<TreeNode>>>) -> Result<i32, ()> {
        match root {
            None => Ok(0), // 空树高度为0，且是平衡的
            Some(node) => {
                // 递归检查左子树
                let left_height = Self::check_balanced(&node.borrow().left)?;
                // 递归检查右子树
                let right_height = Self::check_balanced(&node.borrow().right)?;

                // 检查当前节点是否平衡
                if (left_height - right_height).abs() > 1 {
                    Err(()) // 不平衡立即返回错误
                } else {
                    // 返回当前子树高度（左右子树中较高的+1）
                    Ok(cmp::max(left_height, right_height) + 1)
                }
            }
        }
    }
}

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

paths-tree.jpg

1
2
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

1
2
输入：root = [1]
输出：["1"]

提示：

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

💡 思路：

  1. 遍历二叉树，根节点到叶子节点 → DFS
  2. DFS递归实现：
    a. 确定递归参数：函数需要当前节点，当前路径 - 1（不包含当前节点的路径），结果集作为参数，无返回值
    b. 确定返回条件：当左右子节点都为空时，当前节点为叶子节点，保存当前路径到结果集中，并回溯到上一层
    c. 确定单层递归逻辑：分别判断左右子节点是否为空，同时递归左右子节点

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn binary_tree_paths(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<String> {
        let mut res = Vec::new();
        Self::recursion(root.as_ref().unwrap(), String::from(""), &mut res);
        res
    }

    fn recursion(node: &Rc<RefCell<TreeNode>>, mut path: String, res: &mut Vec<String>) {
        // 处理路径
        let node = node.borrow();
        if path.is_empty() {
            // 为空表示为根节点时
            path.push_str(&node.val.to_string());
        } else {
            path.push_str(&format!("->{}", &node.val.to_string()));
        }

        // 检查左右子节点是否都为空 是 -> 叶子节点 保存路径
        if node.left.is_none() && node.right.is_none() {
            res.push(path);
            return;
        }

        // 递归处理左子节点 如果为Some才处理
        if let Some(left) = &node.left {
            // 这里的clone操作是为了保证当前节点的path不被修改
            // 当这里的里层递归完成，path还是原来的（回溯）
            // 当然，函数传递String类型，rust在检测到右子节点需要path，这里直接使用path也会报错
            // 因为path所有权被转移，不能再使用
            Self::recursion(left, path.clone(), res);
        }

        // 递归处理左子节点 如果为Some才处理
        if let Some(right) = &node.right {
            // 这里不使用clone，因为这里是最后一次使用本层的path，既不违反rust的所有权规则
            // 也不用回溯到原来的path；（因为每层递归都维护了自己的path，
            // 这里最后一次使用就可以不用维护path，保持path不变了）
            Self::recursion(right, path, res);
        }
    }
}

100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

ex1.jpg

1
2
输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

ex2.jpg

1
2
输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

ex3.jpg

1
2
输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

  • 两棵树上的节点数目都在范围 [0, 100] 内
  • -10^4 <= Node.val <= 10^4

💡 思路：递归判断对应节点是否相同

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn is_same_tree(
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>
    ) -> bool {
        match (p, q) {
            (None, None) => true,
            (Some(p), Some(q)) => {
                let p = p.borrow();
                let q = q.borrow();

                p.val == q.val &&
                    Self::is_same_tree(p.left.clone(), q.left.clone()) &&
                    Self::is_same_tree(p.right.clone(), q.right.clone())
            }
            _ => false,
        }
    }
}

572. 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

1724998676-cATjhe-image.png

1
2
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

1724998698-sEJWnq-image.png

1
2
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

  • root 树上的节点数量范围是 [1, 2000]
  • subRoot 树上的节点数量范围是 [1, 1000]
  • -10^4 <= root.val <= 10^4
  • -10^4 <= subRoot.val <= 10^4

💡 思路：前面已经有判断两颗树是否相同：100. 相同的树，我们只需要遍历root树判断两颗树是否相同即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn is_subtree(
        root: Option<Rc<RefCell<TreeNode>>>,
        sub_root: Option<Rc<RefCell<TreeNode>>>
    ) -> bool {
        Self::is_subtree_ref(&root, &sub_root)
    }
		// 新增函数，判断相同不需要所有权，使用引用可提升性能
    fn is_subtree_ref(
        root: &Option<Rc<RefCell<TreeNode>>>,
        sub_root: &Option<Rc<RefCell<TreeNode>>>
    ) -> bool {
        match (root, sub_root) {
            (_, None) => true, // 空树是任何树的子树
            (None, _) => false,
            (Some(root_node), Some(sub_root_node)) => {
                Self::same_tree_ref(root, sub_root) ||
                    Self::is_subtree_ref(&root_node.borrow().left, sub_root) ||
                    Self::is_subtree_ref(&root_node.borrow().right, sub_root)
            }
        }
    }

    fn same_tree_ref(
        t1: &Option<Rc<RefCell<TreeNode>>>,
        t2: &Option<Rc<RefCell<TreeNode>>>
    ) -> bool {
        match (t1, t2) {
            (None, None) => true,
            (Some(t1), Some(t2)) => {
                let t1 = t1.borrow();
                let t2 = t2.borrow();
                t1.val == t2.val &&
                    Self::same_tree_ref(&t1.left, &t2.left) &&
                    Self::same_tree_ref(&t1.right, &t2.right)
            }
            _ => false,
        }
    }
}

404. 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

leftsum-tree.jpg

1
2
3
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

1
2
输入: root = [1]
输出: 0

提示:

  • 节点数在 [1, 1000] 范围内
  • -1000 <= Node.val <= 1000

💡 思路：递归法
将整棵树的左叶子求和分解为先求节点的左叶子值再求和
因为一个节点是不是左叶子，需要通过父节点判断 → 节点为父节点左孩子，且该节点没有左右孩子。所以，遍历时使用遍历节点判断左孩子是否为叶子节点，是的话获取该叶子节点的值。否则递归遍历节点左孩子，获取左叶子值。最后加上遍历节点右孩子获取的左叶子值。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn sum_of_left_leaves(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::sum_of_left_leaves_helper(&root)
    }

		// 辅助函数 用于获取某个节点的左叶子值
    fn sum_of_left_leaves_helper(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match node {
            None => 0, // 如果当前节点为空 返回0
            Some(r) => {
                let node = r.borrow();
                // 使用left_sum 存储左孩子中的左叶子值
                let left_sum = 
                if let Some(left) = &node.left { // 有左孩子
                    let left_node = left.borrow();
                    if left_node.left.is_none() && left_node.right.is_none() { // 左孩子为叶子节点
                        left_node.val // 获取左叶子值
                    } else { // 有左孩子 不为叶子节点
                        Self::sum_of_left_leaves_helper(&node.left) // 递归获取左孩子左叶子值
                    }
                } else {
                    0 // 左孩子为空 返回0
                };
                // 返回左孩子左叶子值 加上 右孩子左叶子值
                left_sum + Self::sum_of_left_leaves_helper(&node.right)
            }
        }
    }
}

可以看到以上函数在处理左叶子时的逻辑十分繁琐，我们可以优化一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn sum_of_left_leaves(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::sum_of_left_leaves_helper(&root, false)
    }

    // 因为判断是否为左叶子时 要先判断是否为左孩子，左孩子需要父节点判断，所以在之前的代码里显得复杂
    // 而我们可以通过传递is_left简化逻辑，左孩子需要父节点判断 -> 在递归里，父节点就是上一层递归
    // 而在调用递归函数时，我们能明确知道下一层递归的节点是否为左孩子，在递归函数参数中传入is_left可简化很多逻辑
    fn sum_of_left_leaves_helper(node: &Option<Rc<RefCell<TreeNode>>>, is_left: bool) -> i32 {
        match node {
            None => 0,
            Some(n) => {
                let node = n.borrow();
                // 是左叶子节点 返回左叶子值
                if is_left && node.left.is_none() && node.right.is_none() {
                    return node.val;
                }

                // 不是左叶子 递归获取左叶子值
                Self::sum_of_left_leaves_helper(&node.left, true) +
                    Self::sum_of_left_leaves_helper(&node.right, false)
            }
        }
    }
}

513. 找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

tree1.jpg

1
2
输入:root = [2,1,3]
输出:1

示例 2:

tree2.jpg

1
2
输入:[1,2,3,4,null,5,6,null,null,7]
输出:7

提示:

  • 二叉树的节点个数的范围是 [1,10^4]
  • -2^31 <= Node.val <= 2^31 - 1

💡 思路：

  1. 题目寻找最底层，最左侧数据 → 用层序遍历 获取最后一层最左侧数据即可
  2. 递归法：
    a. 递归到深度最大的叶子节点
    b. 怎么找最大深度 → 需要一个变量存储最大深度，当当前深度大于最大深度时更新，且这个最大深度变量不能因递归改变（指的是：只能当满足条件时更新。当变量处于递归里时，每个递归状态中会维护一个递归中的变量，我们要将最大深度放在递归外部，防止递归影响）
    c. 最大深度更新时同步更新结果（结果同样要放在递归外部）

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if let Some(root) = root {
            let mut queue = VecDeque::new();
            queue.push_back(root);
            
            let mut left_v = 0;
            while !queue.is_empty() {
                let size = queue.len();
                for i in 0..size {
                    let node = queue.pop_front().unwrap();
                    let node = node.borrow();

                    if i == 0 {
                        left_v = node.val; // 记录每层第一个节点的值
                    }

                    if let Some(left) = &node.left {
                        queue.push_back(left.clone());
                    }

                    if let Some(right) = &node.right {
                        queue.push_back(right.clone());
                    }
                }
            }

            left_v
        } else {
            0
        }
    }
}

代码（思路二）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut res = 0; // 结果 存放在递归外
        let mut max_depth = 0; // 最大深度 存放在递归外
        Self::recur(&root, 1, &mut max_depth, &mut res);
        res
    }

    fn recur(node: &Option<Rc<RefCell<TreeNode>>>, depth: i32, max_depth: &mut i32, res: &mut i32) {
        if let Some(n) = node {
            // 如果当前节点不为空
            let node = n.borrow();

            // 当当前深度 > 最大深度 更新最大深度以及结果
            if depth > *max_depth {
                *max_depth = depth;
                *res = node.val;
            }

            // 先递归左节点，因为在更新最大深度和结果时
            // 每层只会更新一次，必须先处理左节点才能保证最后是最深层的最左节点
            Self::recur(&node.left, depth + 1, max_depth, res);
            Self::recur(&node.right, depth + 1, max_depth, res);
        }
    }
}

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：

pathsum1.jpg

1
2
3
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

pathsum2.jpg

1
2
3
4
5
6
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

1
2
3
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

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

💡 思路：递归，进行DFS，当路径和为题目要求的时，返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn has_path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
        Self::recur(&root, target_sum)
    }
		
		// 使用引用进行遍历
    fn recur(node: &Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool{
        if let Some(node) = node { // 不是空节点
            let node = node.borrow();
            
            // 是叶子节点
            if node.left.is_none() && node.right.is_none() {
                node.val == target_sum // 判断是否符合要求
            } else {
		            // 使用 target_sum - node.val 当 node.val == target_sum 满足要求
                Self::recur(&node.left, target_sum - node.val) 
		                // 使用 || 运算符，当为true时直接短路返回
                    || Self::recur(&node.right, target_sum - node.val)
            }
        } else {
            false // 空节点 返回false 代表从跟节点到该节点都不满足题目要求
        }
    }
}

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

pathsumii1.jpg

1
2
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

pathsum2.jpg

1
2
输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

1
2
输入：root = [1,2], targetSum = 0
输出：[]

提示：

  • 树中节点总数在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

💡 思路：递归，使用DFS进行记录路径，当且仅当节点为叶子几点，节点路径值之和满足条件时，记录路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> Vec<Vec<i32>> {
        let mut res = vec![];
        let mut path = vec![];
        Self::dfs(&root, target_sum, &mut path, &mut res);
        res
    }

    // 深度优先搜索
    fn dfs(
        node: &Option<Rc<RefCell<TreeNode>>>, // 当前节点
        target_sum: i32, // 所需求值
        path: &mut Vec<i32>, // 当前路径 不包含本节点
        res: &mut Vec<Vec<i32>> // 记录结果
    ) {
        if let Some(node) = node {
            let node = node.borrow();
            path.push(node.val); // 加入当前节点
            let remaining = target_sum - node.val; // 计算还需要的剩余值

            // 检查是否是满足条件的叶子节点
            if node.left.is_none() && node.right.is_none() {
                if remaining == 0 {
                    res.push(path.clone());
                }
            } else {
                Self::dfs(&node.left, remaining, path, res);
                Self::dfs(&node.right, remaining, path, res);
            }

            path.pop(); // 统一回溯
        }
    }
}

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

tree.jpg

1
2
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

1
2
输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -1000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

💡 思路：

  1. 后序遍历特点：最后一个元素是根节点
  2. 中序遍历特点：根节点左侧是左子树，右侧是右子树
  3. 递归构建：
    a. 从后序确定根节点
    b. 在中序中找到根节点位置
    c. 划分左右子树
    d. 递归构建左右子树

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn build_tree(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        Self::build_helper(&inorder, &postorder)
    }

    fn build_helper(inorder: &[i32], postorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
        // 第一步： 判断是否为空数组
        if inorder.is_empty() {
            return None;
        }

        // 第二步： 获取后续遍历最后一个元素作为节点元素
        let root_val = *postorder.last().unwrap();
        let root = Rc::new(RefCell::new(TreeNode::new(root_val)));
        // 如果数组中只有一个元素 那该元素就是叶子节点 直接返回 (提升性能)
        if postorder.len() == 1 {
            return Some(root);
        }

        // 第三步： 找到该节点在中序数组中的位置
        let root_pos = inorder.iter().position(|&x| x == root_val).unwrap();
        
        // 第四步： 根据位置，分割中序数组为中序左数组和中序右数组
        let inorder_left =  &inorder[..root_pos];
        let inorder_right = &inorder[root_pos + 1..];
        
        // 第五步： 分割后序数组为后续左数组和后续右数组
        let postorder_left =  &postorder[..root_pos]; // 长度等于中序左数组 因为都是左子树
        let postorder_right = &postorder[root_pos..postorder.len() - 1];
    
        // 第六步： 递归地处理左区间和右区间
        root.borrow_mut().left = Self::build_helper(inorder_left, postorder_left);
        root.borrow_mut().right = Self::build_helper(inorder_right, postorder_right);

        Some(root)
    }
}

可以看到在每次递归中都循环查找位置（第3步），可以优化一下，使用哈希表可以达到O(1)的查找效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;
impl Solution {
    pub fn build_tree(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        // 构建哈希表
        let index_map: HashMap<_, _> = inorder
            .iter()
            .enumerate()
            .map(|(i, &val)| (val, i))
            .collect();
        Self::build_helper(&inorder[..], &postorder[..], &index_map)
    }

    fn build_helper(
        inorder: &[i32],
        postorder: &[i32],
        index_map: &HashMap<i32, usize>
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if inorder.is_empty() {
            return None;
        }

        let root_val = *postorder.last().unwrap();
        // 从哈希表中获取数据 因为每次递归都会缩小数组 我们要的是缩小后数组的下标
        // 所以root_pos应该是 root_val在完整数组的下标 - 当前数组开头元素在完整数组的下标
        let root_pos = index_map[&root_val] - index_map[&inorder[0]];

        let mut root = Rc::new(RefCell::new(TreeNode::new(root_val)));
        if postorder.len() == 1 {
            return Some(root);
        }

        let inorder_left = &inorder[..root_pos];
        let inorder_right = &inorder[root_pos + 1..];

        let postorder_left = &postorder[..root_pos];
        let postorder_right = &postorder[root_pos..postorder.len() - 1];

        root.borrow_mut().left = Self::build_helper(inorder_left, postorder_left, index_map);
        root.borrow_mut().right = Self::build_helper(inorder_right, postorder_right, index_map);

        Some(root)
    }
}

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

tree.jpg

1
2
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

1
2
输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

💡 思路：同106. 从中序与后序遍历序列构造二叉树

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;
impl Solution {
    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        let index_map: HashMap<i32, usize> = inorder.iter().enumerate().map(|(i, &v)| (v, i)).collect();
        Self::build_helper(&preorder, &inorder, &index_map)
    }

    fn build_helper(
        preorder: &[i32],
        inorder: &[i32],
        index_map: &HashMap<i32, usize>
    )-> Option<Rc<RefCell<TreeNode>>>{
        if preorder.is_empty() { return None; }

        let root_val = *preorder.first().unwrap();
        let root_node = Rc::new(RefCell::new(TreeNode::new(root_val)));
        if preorder.len() == 1 {
            return Some(root_node);
        }

        let root_pos = index_map[&root_val] - index_map[&inorder[0]];

        root_node.borrow_mut().left = Self::build_helper(
            &preorder[1..root_pos + 1],
            &inorder[..root_pos],
            index_map
        );

        root_node.borrow_mut().right = Self::build_helper(
            &preorder[root_pos + 1..],
            &inorder[root_pos + 1..],
            index_map
        );

        Some(root_node)
    }
}

654. 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例 1：

tree1.jpg

1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

tree2.jpg

1
2
输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • nums 中的所有整数 互不相同

💡 思路：看题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        Self::construct_helper(&nums)
    }

    fn construct_helper(nums: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
        if nums.is_empty() { return None; }
        let mut max = nums[0];
        let mut index_max = 0;
        for i in 1..nums.len() {
            if nums[i] > max {
                max = nums[i];
                index_max = i;
            }
        }

        let root = Rc::new(RefCell::new(TreeNode::new(max)));
        if nums.len() == 1 {
            return Some(root);
        }

        root.borrow_mut().left = Self::construct_helper(&nums[..index_max]);
        root.borrow_mut().right = Self::construct_helper(&nums[index_max + 1..]);

        Some(root)
    }
}