算法题/树的DFS：某个和的所有路径

题目

给定一棵二叉树和一个数字'S'，找出从根到叶的所有路径，使每个路径的所有节点值之和等于'S'。

解答

Java

import java.util.*;

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
};

class FindAllTreePaths {
  public static List<List<Integer>> findPaths(TreeNode root, int sum) {
    List<List<Integer>> allPaths = new ArrayList<>();
    List<Integer> currentPath = new ArrayList<Integer>();
    findPathsRecursive(root, sum, currentPath, allPaths);
    return allPaths;
  }

  private static void findPathsRecursive(TreeNode currentNode, int sum, List<Integer> currentPath,
      List<List<Integer>> allPaths) {
    if (currentNode == null)
      return;

    // 添加当前节点到路径中
    currentPath.add(currentNode.val);

    // 如果当前节点是叶子结点并且它的值等于当前总和sum，保存当前路径
    if (currentNode.val == sum && currentNode.left == null && currentNode.right == null) {
      allPaths.add(new ArrayList<Integer>(currentPath));
    } else {
      // 遍历左子树
      findPathsRecursive(currentNode.left, sum - currentNode.val, currentPath, allPaths);
      // 遍历右子树
      findPathsRecursive(currentNode.right, sum - currentNode.val, currentPath, allPaths);
    }

    // 从要回溯的路径中删除当前节点 
    // 当我们向上递归调用堆栈时，我们需要删除当前节点。
    currentPath.remove(currentPath.size() - 1);
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(12);
    root.left = new TreeNode(7);
    root.right = new TreeNode(1);
    root.left.left = new TreeNode(4);
    root.right.left = new TreeNode(10);
    root.right.right = new TreeNode(5);
    int sum = 23;
    List<List<Integer>> result = FindAllTreePaths.findPaths(root, sum);
    System.out.println("Tree paths with sum " + sum + ": " + result);
  }
}

JavaScript

class TreeNode {
  constructor(x) {
    this.val = x;
    this.left = null;
    this.right = null;
  }
}

class FindAllTreePaths {
  static findPaths(root, sum) {
    const allPaths = [];
    const currentPath = [];
    FindAllTreePaths.findPathsRecursive(root, sum, currentPath, allPaths);
    return allPaths;
  }

  static findPathsRecursive(currentNode, sum, currentPath, allPaths) {
    if (currentNode === null) {
      return;
    }

    // 添加当前节点到路径中
    currentPath.push(currentNode.val);

    // 如果当前节点是叶子结点并且它的值等于当前总和sum，保存当前路径
    if (currentNode.val === sum && currentNode.left === null && currentNode.right === null) {
      allPaths.push([...currentPath]);
    } else {
      // 遍历左子树
      FindAllTreePaths.findPathsRecursive(currentNode.left, sum - currentNode.val, currentPath, allPaths);
      // 遍历右子树
      FindAllTreePaths.findPathsRecursive(currentNode.right, sum - currentNode.val, currentPath, allPaths);
    }

    // 从要回溯的路径中删除当前节点 
    // 当我们向上递归调用堆栈时，我们需要删除当前节点。
    currentPath.pop();
  }
}

const root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(1);
root.left.left = new TreeNode(4);
root.right.left = new TreeNode(10);
root.right.right = new TreeNode(5);
const sum = 23;
const result = FindAllTreePaths.findPaths(root, sum);
console.log(`Tree paths with sum ${sum}:`, result);

Python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class FindAllTreePaths:
    @staticmethod
    def findPaths(root, sum):
        allPaths = []
        currentPath = []
        FindAllTreePaths.findPathsRecursive(root, sum, currentPath, allPaths)
        return allPaths

    @staticmethod
    def findPathsRecursive(currentNode, sum, currentPath, allPaths):
        if currentNode is None:
            return

        # 添加当前节点到路径中
        currentPath.append(currentNode.val)

        # 如果当前节点是叶子结点并且它的值等于当前总和sum，保存当前路径
        if currentNode.val == sum and currentNode.left is None and currentNode.right is None:
            allPaths.append(list(currentPath))
        else:
            # 遍历左子树
            FindAllTreePaths.findPathsRecursive(currentNode.left, sum - currentNode.val, currentPath, allPaths)
            # 遍历右子树
            FindAllTreePaths.findPathsRecursive(currentNode.right, sum - currentNode.val, currentPath, allPaths)

        # 从要回溯的路径中删除当前节点
        # 当我们向上递归调用堆栈时，我们需要删除当前节点。
        currentPath.pop()

root = TreeNode(12)
root.left = TreeNode(7)
root.right = TreeNode(1)
root.left.left = TreeNode(4)
root.right.left = TreeNode(10)
root.right.right = TreeNode(5)
sum = 23
result = FindAllTreePaths.findPaths(root, sum)
print("Tree paths with sum", sum, ":", result)

Go

package main

import "fmt"

type TreeNode struct {
	val   int
	left  *TreeNode
	right *TreeNode
}

func findPaths(root *TreeNode, sum int) [][]int {
	allPaths := [][]int{}
	currentPath := []int{}
	findPathsRecursive(root, sum, currentPath, &allPaths)
	return allPaths
}

func findPathsRecursive(currentNode *TreeNode, sum int, currentPath []int, allPaths *[][]int) {
	if currentNode == nil {
		return
	}

	// 添加当前节点到路径中
	currentPath = append(currentPath, currentNode.val)

	// 如果当前节点是叶子结点并且它的值等于当前总和sum，保存当前路径
	if currentNode.val == sum && currentNode.left == nil && currentNode.right == nil {
		*allPaths = append(*allPaths, append([]int{}, currentPath...))
	} else {
		// 遍历左子树
		findPathsRecursive(currentNode.left, sum-currentNode.val, currentPath, allPaths)
		// 遍历右子树
		findPathsRecursive(currentNode.right, sum-currentNode.val, currentPath, allPaths)
	}

	// 从要回溯的路径中删除当前节点
	// 当我们向上递归调用堆栈时，我们需要删除当前节点。
	currentPath = currentPath[:len(currentPath)-1]
}

func main() {
	root := &TreeNode{val: 12}
	root.left = &TreeNode{val: 7}
	root.right = &TreeNode{val: 1}
	root.left.left = &TreeNode{val: 4}
	root.right.left = &TreeNode{val: 10}
	root.right.right = &TreeNode{val: 5}
	sum := 23
	result := findPaths(root, sum)
	fmt.Println("Tree paths with sum", sum, ":", result)
}