Interview Classic 150 Questions P129 Sum of Root-to-Leaf Numbers

---

Timeline

timeline

2025-10-28

init

depth-first traversal

---

Problem:

P129 Sum of Root-to-Leaf Numbers

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

Depth-first traversal, using pre-order, in-order, or post-order traversal of the tree are all acceptable. Here we choose pre-order traversal.

✔ Pre-order traversal ⊂ depth-first traversal
✘ ButDFS ≠ only pre-order traversal, it also has two other forms: in-order and post-order.

More specifically:

Traversal method	Belongs to DFS?	Order description (for binary tree)
Preorder traversal (Preorder)	Is DFS	Root → Left → Right
Inorder traversal (Inorder)	Is DFS	Left → Root → Right
Postorder traversal (Postorder)	Is DFS	Left → Right → Root

// 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 {
        // Depth-first traversal
        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
    }
}

Depth-first search

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);
    }
};