剑指offer-题25：二叉树中和为某一值的路径

谁践踏了优雅 2022-05-29 12:28 114阅读 0赞

## **题目描述** ##

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

实验平台：[牛客网][Link 1]

--------------------

## **解决思路：** ##

![这里写图片描述][70]  
![这里写图片描述][70 1]  
![这里写图片描述][70 2]  
![这里写图片描述][70 3]  
![这里写图片描述][70 4]

java:

import java.util.ArrayList;
    import java.util.Stack;
    /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        int curSum = 0;
        Stack<Integer> pathStack = new Stack<>();
        ArrayList<ArrayList<Integer>> pathList = new ArrayList<>();
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
            if (root == null) {
                return pathList;
            }
            curSum += root.val;
            pathStack.push(root.val);
    
            boolean isLeafNode = root.left == null && root.right == null;
            if (curSum == target && isLeafNode) {
                ArrayList<Integer> path = new ArrayList<Integer>();
                for (Integer value : pathStack) {
                    path.add(value);
                }
                pathList.add(path);
            }
            if (root.left != null) {
                FindPath(root.left, target);
            }
            if (root.right != null) {
                FindPath(root.right, target);
            }
            pathStack.pop();
            curSum -= root.val;
            return pathList;
        }
    }

python:

# -*- coding:utf-8 -*-
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    class Solution:
        path_list = []
        stack = []
        cur_sum = 0
        # 返回二维列表，内部每个列表表示找到的路径
        def FindPath(self, root, expectNumber):
            self.path_list = []
            self.stack = []
            self.cur_sum = 0
            return self.get_path(root, expectNumber)
    
        def get_path(self, root, expectNumber):
            if root is None:
                return self.path_list
            self.cur_sum += root.val
            self.stack.append(root.val)
    
            is_leaf = root.right is None and root.left is None
            if self.cur_sum == expectNumber and is_leaf:
                temp_path = self.stack[:]
                self.path_list.append(temp_path)
            if root.left:
                self.get_path(root.left, expectNumber)
            if root.right:
                self.get_path(root.right, expectNumber)
            self.stack.pop()
            self.cur_sum -= root.val
            return self.path_list

[Link 1]: https://www.nowcoder.com/ta/coding-interviews?page=1
[70]: /images/20220529/9a04ae26630b4d02aef0b122cade5399.png
[70 1]: /images/20220529/9da731ad9a1b4902a19ac782e7a54eae.png
[70 2]: /images/20220529/84b93386f1444127882fd8e2666a2e8e.png
[70 3]: /images/20220529/f605cc65f4aa4ff1858564307fa52501.png
[70 4]: /images/20220529/9d1f87ccdbbd42968a3a98bf6be7c6cf.png