面试经典150题 P129 求根节点到叶节点数字之和

---

时间轴

时间轴

2025-10-28

init

深度优先遍历

---

题目：

P129 求根节点到叶节点数字之和

https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/?envType=study-plan-v2&envId=top-interview-150

深度优先遍历，用树的先序遍历，中序遍历，后序遍历均可。这里选择先序遍历。

✔ 先序遍历 ⊂ 深度优先遍历
✘ 但 DFS ≠ 只有先序遍历，它还有另外两种形式：中序和后序。

更具体地说：

遍历方式	属于 DFS 吗	顺序描述（对二叉树）
前序遍历 (Preorder)	是 DFS	根 → 左 → 右
中序遍历 (Inorder)	是 DFS	左 → 根 → 右
后序遍历 (Postorder)	是 DFS	左 → 右 → 根

// Definition for a binary tree node.
struct Solution;
#[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,
        }
    }
}
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
    pub fn sum_numbers(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        // 深度优先遍历
        let mut stack = VecDeque::new();
        let mut sum = 0;
        
        if let Some(node) = root {
            let val = node.borrow().val;
            stack.push_back((node, val));
        } else {
            return 0;
        }

        while let Some((node, val)) = stack.pop_back() {
            let node_ref = node.borrow();
            if node_ref.left.is_none() && node_ref.right.is_none() {
                sum += val;
            }
            if let Some(right) = node_ref.right.clone() {
                let right_val = right.borrow().val;
                stack.push_back((right, val * 10 + right_val));
            }

            if let Some(left) = node_ref.left.clone() {
                let left_val = left.borrow().val;
                stack.push_back((left, val * 10 + left_val));
            }
        }
        sum
    }
}

深度优先搜索

class Solution {
public:
    int dfs(TreeNode* root, int prevSum) {
        if (root == nullptr) return 0;
        
        int sum = prevSum * 10 + root->val;
        
        if (root->left == nullptr && root->right == nullptr)
            return sum;
        else
            return dfs(root->left, sum) + dfs(root->right, sum);        
    }
    
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};