华企号 元宇宙 二叉树中和为某一值的路径

二叉树中和为某一值的路径

JZ34 二叉树中和为某一值的路径(二)

描述

输入一颗二叉树的根节点root和一个整数expectNumber,找出二叉树中结点值的和为expectNumber的所有路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点,不能从子节点到父节点
4.总节点数目为n

思路

当前的路径path要更新
当前的目标值expectNumber要迭代,减去当前节点的值
若当前节点是叶子节点,考虑是否满足路径的期待值,并考虑是否将路径添加到返回列表中
具体做法:

step 1:维护两个向量ret和path
step 2:编写递归函数dfs
step 3:递归函数内部要处理更新path,更新expectNumber,判断是否为叶子节点和判断是否要将path追加到ret末尾

代码

package mid.JZ34二叉树中和为某一值的路径2;

import java.util.ArrayList;
import java.util.LinkedList;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

public class Solution {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        dfs(root,expectNumber);
        return ret;
    }

    public void dfs(TreeNode root, int expectNumber) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        expectNumber -= root.val;
        if (root.left == null && root.right == null && expectNumber == 0) {
            ret.add(new ArrayList<>(path));
        }

        dfs(root.left, expectNumber);
        dfs(root.right, expectNumber);

        path.removeLast();
    }
}

作者: 华企网通王鹏程序员

我是程序员王鹏,热爱互联网软件开发和设计,专注于大数据、数据分析、数据库、php、java、python、scala、k8s、docker等知识总结。 我的座右铭:"业精于勤荒于嬉,行成于思毁于随"
上一篇
下一篇

发表回复

联系我们

联系我们

028-84868647

在线咨询: QQ交谈

邮箱: tech@68v8.com

工作时间:周一至周五,9:00-17:30,节假日休息

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部