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

名字是乱打的

发布于 2022-05-13 09:15:07

2440

发布于 2022-05-13 09:15:07

文章被收录于专栏：软件工程

题目描述

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 (注意: 在返回值的list中，数组长度大的数组靠前)

思路:

当前结点情况分三种 1.null.直接返回 2.叶子结点(左右孩子均为null),进行判断 3.非叶子结点,将当前sum以及node装配到下一个结点继续判断 4.除了空结点,我们只要添加了结点,最后必然要退一个结点(arr删除一个结点),到上一步

有两个需要注意的点 1.如果arr直接添加到arrs的话而不是创建一个新arr进行添加，后面对list的remove操作就会影响listAll里面的元素了 2.除了空结点,我们只要添加了结点,最后必然要退一个结点(arr删除一个结点),到上一步,因为我们传的arr是地址传递,只有删掉最后一个结点,这样我们才可以返回上一步的状态进行操作,不然每次都会加结点.

代码

package com.algorithm.offer;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

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

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

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        ArrayList<ArrayList<Integer>> arrs = new ArrayList<>();
        ArrayList<Integer> arr = new ArrayList<>();
        addPath(root, target, 0, arr, arrs);
        Collections.sort(arrs, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> arr1, ArrayList<Integer> arr2) {
                return arr2.size()-arr1.size();
            }
        });
        return arrs;
    }


    public void addPath(TreeNode CurrNode, int target, int sum, ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> arrs) {
        if (CurrNode==null){
            return;
        }
        if (CurrNode.left == null&&CurrNode.right==null) {
            sum += CurrNode.val;
            arr.add(CurrNode.val);
            if (sum == target) {
                arrs.add(new ArrayList<Integer>(arr));
                arr.remove(arr.size()-1);
            }else {
                arr.remove(arr.size()-1);
                return;
            }
        } else {
            sum += CurrNode.val;
            arr.add(CurrNode.val);
            addPath(CurrNode.left, target, sum, arr, arrs);
            addPath(CurrNode.right, target, sum, arr, arrs);
            arr.remove(arr.size()-1);
        }
    }

    @Test
    public void test() {
        TreeNode head=new TreeNode(5);
        head.left=new TreeNode(4);
        head.left.left=new TreeNode(3);
        head.left.left.left=new TreeNode(2);
        head.left.left.left.left=new TreeNode(1);
        ArrayList<ArrayList<Integer>> arrs = FindPath(head, 15);
        for (ArrayList<Integer> arr: arrs
             ) {
            for (Integer i:arr
                 ) {
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }
    



}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-05-13，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树