大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题34. 二叉树中和为某一值的路径

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

提示:

  • 节点总数 <= 10000

二、题目解析

这道题目明确给出了路径的起始位置是在二叉树的根节点,直到延伸至叶子节点,如果想得到所有根节点到叶子结点的路径,需要遍历整棵树。

由于从根节点开始,所以采取前序遍历

当用前序遍历访问到某一节点时,把当前节点添加到路径上,同时累加该节点的值,再进行一次判断:

  • 如果当前节点为叶子节点,并且路径中所有节点的值之和等于输入的目标值,则当前路径符合要求,把路径加入到结果数组中;
  • 如果当前节点为叶子节点,当路径中所有节点的值之和不等于输入的目标值,则需要回溯到它的父节点
  • 如果当前节点不是叶子节点,则继续访问它的左右子节点。

三、动画描述

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、图片描述

剑指 Offer 34. 二叉树中和为某一值的路径.002

剑指 Offer 34. 二叉树中和为某一值的路径.003

剑指 Offer 34. 二叉树中和为某一值的路径.004

剑指 Offer 34. 二叉树中和为某一值的路径.005

剑指 Offer 34. 二叉树中和为某一值的路径.006

剑指 Offer 34. 二叉树中和为某一值的路径.007

剑指 Offer 34. 二叉树中和为某一值的路径.008

剑指 Offer 34. 二叉树中和为某一值的路径.009

剑指 Offer 34. 二叉树中和为某一值的路径.010

剑指 Offer 34. 二叉树中和为某一值的路径.011

剑指 Offer 34. 二叉树中和为某一值的路径.012

剑指 Offer 34. 二叉树中和为某一值的路径.013

剑指 Offer 34. 二叉树中和为某一值的路径.014

剑指 Offer 34. 二叉树中和为某一值的路径.015

剑指 Offer 34. 二叉树中和为某一值的路径.016

剑指 Offer 34. 二叉树中和为某一值的路径.017

剑指 Offer 34. 二叉树中和为某一值的路径.018

剑指 Offer 34. 二叉树中和为某一值的路径.019

剑指 Offer 34. 二叉树中和为某一值的路径.020

剑指 Offer 34. 二叉树中和为某一值的路径.021

剑指 Offer 34. 二叉树中和为某一值的路径.022

剑指 Offer 34. 二叉树中和为某一值的路径.023

剑指 Offer 34. 二叉树中和为某一值的路径.024

剑指 Offer 34. 二叉树中和为某一值的路径.025

剑指 Offer 34. 二叉树中和为某一值的路径.026

剑指 Offer 34. 二叉树中和为某一值的路径.027

剑指 Offer 34. 二叉树中和为某一值的路径.028

剑指 Offer 34. 二叉树中和为某一值的路径.029

剑指 Offer 34. 二叉树中和为某一值的路径.030

剑指 Offer 34. 二叉树中和为某一值的路径.031

剑指 Offer 34. 二叉树中和为某一值的路径.032

剑指 Offer 34. 二叉树中和为某一值的路径.033

剑指 Offer 34. 二叉树中和为某一值的路径.034

剑指 Offer 34. 二叉树中和为某一值的路径.035

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {

    // res 存放所有满足要求的路径
    LinkedList<List<Integer>> res = new LinkedList<>();
    // path 为正在遍历的路径
    LinkedList<Integer> path = new LinkedList<>(); 

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        // 前序遍历二叉树
        // 此时路径上的和为 0
        findPath(root, sum,0);
        return res;
    }

    // curPathSum 表示 path 路径上的和
    void findPath(TreeNode root, int tar,int curPathSum) {

        // 访问到叶子节点的时候返回
        if(root == null) return;

        // 把当前节点添加到路径上
        path.add(root.val);

        //同时累加该节点的值
        curPathSum += root.val;

        // 1、当前节点为叶子节点
        // 2、路径中所有节点的值之和等于输入的目标值
        // 当前路径符合要求,把路径加入到结果数组中
        if(tar == curPathSum && root.left == null && root.right == null){
            // 需要创建一个新的对象 path 来拷贝全局的 path 再添加到 res 中,因为全局的 path 一直在变化
            // 如果直接添加全局的 path,会导致结果 res 中所有的 path 都是一样的
            res.add(new LinkedList(path));
        }
        // 继续访问它的左子节点    
        findPath(root.left, tar,curPathSum);
        // 继续访问它的右子节点
        findPath(root.right, tar,curPathSum);

        // 访问完当前节点 需要删除路径中最后一个节点,回退至父节点
        path.removeLast();
    }

}

六、复杂度分析

时间复杂度

时间复杂度为 O(N)。

空间复杂度

空间复杂度为 O(N)。

七、相关标签

  • 搜索二叉树
  • 深度优先搜索

发表评论

邮箱地址不会被公开。 必填项已用*标注