Skip to content

Latest commit

 

History

History
389 lines (318 loc) · 10.9 KB

0129.求根到叶子节点数字之和.md

File metadata and controls

389 lines (318 loc) · 10.9 KB

参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!

129. 求根节点到叶节点数字之和

力扣题目链接

思路

本题和113.路径总和II是类似的思路,做完这道题,可以顺便把113.路径总和II112.路径总和 做了。

结合112.路径总和 和 113.路径总和II,我在讲了二叉树:递归函数究竟什么时候需要返回值,什么时候不要返回值?,如果大家对二叉树递归函数什么时候需要返回值很迷茫,可以看一下。

接下来在看本题,就简单多了,本题其实需要使用回溯,但一些同学可能都不知道自己用了回溯,在二叉树:以为使用了递归,其实还隐藏着回溯中,我详细讲解了二叉树的递归中,如何使用了回溯。

接下来我们来看题:

首先思路很明确,就是要遍历整个树把更节点到叶子节点组成的数字相加。

那么先按递归三部曲来分析:

递归三部曲

如果对递归三部曲不了解的话,可以看这里:二叉树:前中后递归详解

  • 确定递归函数返回值及其参数

这里我们要遍历整个二叉树,且需要要返回值做逻辑处理,所有返回值为void,在二叉树:递归函数究竟什么时候需要返回值,什么时候不要返回值?中,详细讲解了返回值问题。

参数只需要把根节点传入,此时还需要定义两个全局遍历,一个是result,记录最终结果,一个是vector path。

为什么用vector类型(就是数组)呢? 因为用vector方便我们做回溯!

所以代码如下:

int result;
vector<int> path;
void traversal(TreeNode* cur) 
  • 确定终止条件

递归什么时候终止呢?

当然是遇到叶子节点,此时要收集结果了,通知返回本层递归,因为单条路径的结果使用vector,我们需要一个函数vectorToInt把vector转成int。

终止条件代码如下:

if (!cur->left && !cur->right) { // 遇到了叶子节点
    result += vectorToInt(path);
    return;
}

这里vectorToInt函数就是把数组转成int,代码如下:

int vectorToInt(const vector<int>& vec) {
    int sum = 0;
    for (int i = 0; i < vec.size(); i++) {
        sum = sum * 10 + vec[i];
    }
    return sum;
}
  • 确定递归单层逻辑

本题其实采用前中后序都不无所谓, 因为也没有中间几点的处理逻辑。

这里主要是当左节点不为空,path收集路径,并递归左孩子,右节点同理。

但别忘了回溯

如图:

代码如下:

                 //
if (cur->left) { // 左 (空节点不遍历)
    path.push_back(cur->left->val);
    traversal(cur->left);    // 递归
    path.pop_back();         // 回溯
}
if (cur->right) { // 右 (空节点不遍历)
    path.push_back(cur->right->val);
    traversal(cur->right);   // 递归
    path.pop_back();         // 回溯
}

这里要注意回溯和递归要永远在一起,一个递归,对应一个回溯,是一对一的关系,有的同学写成如下代码:

if (cur->left) { // 左 (空节点不遍历)
    path.push_back(cur->left->val);
    traversal(cur->left);    // 递归
}
if (cur->right) { // 右 (空节点不遍历)
    path.push_back(cur->right->val);
    traversal(cur->right);   // 递归
}
path.pop_back();         // 回溯

把回溯放在花括号外面了,世界上最遥远的距离,是你在花括号里,而我在花括号外! 这就不对了。

整体C++代码

关键逻辑分析完了,整体C++代码如下:

class Solution {
private:
    int result;
    vector<int> path;
    // 把vector转化为int
    int vectorToInt(const vector<int>& vec) {
        int sum = 0;
        for (int i = 0; i < vec.size(); i++) {
            sum = sum * 10 + vec[i];
        }
        return sum;
    }
    void traversal(TreeNode* cur) {
        if (!cur->left && !cur->right) { // 遇到了叶子节点
            result += vectorToInt(path);
            return;
        }

        if (cur->left) { // 左 (空节点不遍历)
            path.push_back(cur->left->val);     // 处理节点
            traversal(cur->left);               // 递归
            path.pop_back();                    // 回溯,撤销
        }
        if (cur->right) { // 右 (空节点不遍历)
            path.push_back(cur->right->val);    // 处理节点
            traversal(cur->right);              // 递归
            path.pop_back();                    // 回溯,撤销
        }
        return ;
    }
public:
    int sumNumbers(TreeNode* root) {
        path.clear();
        if (root == nullptr) return 0;
        path.push_back(root->val);
        traversal(root);
        return result;
    }
};

总结

过于简洁的代码,很容易让初学者忽视了本题中回溯的精髓,甚至作者本身都没有想清楚自己用了回溯。

我这里提供的代码把整个回溯过程充分体现出来,希望可以帮助大家看的明明白白!

其他语言版本

Java:

class Solution {
    List<Integer> path = new ArrayList<>();
    int res = 0;
    public int sumNumbers(TreeNode root) {
        // 如果节点为0,那么就返回0
        if (root == null) return 0;
        // 首先将根节点放到集合中
        path.add(root.val);
        // 开始递归
        recur(root);
        return res;
    }

    public void recur(TreeNode root){
        if (root.left == null && root.right == null) {
            // 当是叶子节点的时候,开始处理
            res += listToInt(path);
            return;
        }

        if (root.left != null){
            // 注意有回溯
            path.add(root.left.val);
            recur(root.left);
            path.remove(path.size() - 1);
        }
        if (root.right != null){
            // 注意有回溯
            path.add(root.right.val);
            recur(root.right);
            path.remove(path.size() - 1);
        }
        return;
    }
    public int listToInt(List<Integer> path){
        int sum = 0;
        for (Integer num:path){
            // sum * 10 表示进位
            sum = sum * 10 + num;
        }
        return sum;
    }
}

Python:

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        res = 0
        path = []
        def backtrace(root):
            nonlocal res
            if not root: return # 节点空则返回
            path.append(root.val)
            if not root.left and not root.right: # 遇到了叶子节点
                res += get_sum(path)
            if root.left: # 左子树不空
                backtrace(root.left)
            if root.right: # 右子树不空
                backtrace(root.right)
            path.pop()

        def get_sum(arr):
            s = 0
            for i in range(len(arr)):
                s = s * 10 + arr[i]
            return s

        backtrace(root)
        return res

Go:

func sumNumbers(root *TreeNode) int {
    sum := 0
    dfs(root, root.Val, &sum)
    return sum
}

func dfs(root *TreeNode, tmpSum int, sum *int) {
    if root.Left == nil && root.Right == nil {
        *sum += tmpSum
    } else {
        if root.Left != nil {
            dfs(root.Left, tmpSum*10 + root.Left.Val, sum)
        }
        if root.Right != nil {
            dfs(root.Right, tmpSum*10 + root.Right.Val, sum)
        }
    }
}

JavaScript:

var sumNumbers = function(root) {
    const listToInt = path => {
        let sum = 0;
        for(let num of path){
            // sum * 10 表示进位
            sum = sum * 10 + num;
        }
        return sum;
    }
    const recur = root =>{
        if (root.left == null && root.right == null) {
            // 当是叶子节点的时候,开始处理
            res += listToInt(path);
            return;
        }

        if (root.left != null){
            // 注意有回溯
            path.push(root.left.val);
            recur(root.left);
            path.pop();
        }
        if (root.right != null){
            // 注意有回溯
            path.push(root.right.val);
            recur(root.right);
            path.pop();
        }
        return;
    };
    const path = new Array();
    let res = 0;
    // 如果节点为0,那么就返回0
    if (root == null) return 0;
    // 首先将根节点放到集合中
    path.push(root.val);
    // 开始递归
    recur(root);
    return res;
};

TypeScript:

function sumNumbers(root: TreeNode | null): number {
    if (root === null) return 0;
    // 记录最终结果
    let resTotal: number = 0;
    // 记录路径中遇到的节点值
    const route: number[] = [];
    // 递归初始值
    route.push(root.val);
    recur(root, route);
    return resTotal;
    function recur(node: TreeNode, route: number[]): void {
        if (node.left === null && node.right === null) {
            resTotal += listToSum(route);
            return;
        }
        if (node.left !== null) {
            route.push(node.left.val);
            recur(node.left, route);
            route.pop();
        };
        if (node.right !== null) {
            route.push(node.right.val);
            recur(node.right, route);
            route.pop();
        };
    }
    function listToSum(nums: number[]): number {
        // 数组求和
        return Number(nums.join(''));
    }
};

C:

//sum记录总和
int sum;
void traverse(struct TreeNode *node, int val) {
    //更新val为根节点到当前节点的和
    val = val * 10 + node->val;
    //若当前节点为叶子节点,记录val
    if(!node->left && !node->right) {
        sum+=val;
        return;
    }
    //若有左/右节点,遍历左/右节点
    if(node->left) 
        traverse(node->left, val);
    if(node->right)
        traverse(node->right, val);
}

int sumNumbers(struct TreeNode* root){
    sum = 0;
    
    traverse(root, 0);

    return sum;
}