算法题/树的DFS：路径代表的数之和

题目

给定一个二叉树，其中每个节点只能有一个数字(0-9)值，每个根到叶路径将代表一个数字。找出所有路径所代表的所有数字的总和。

解答

Java

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

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

class SumOfPathNumbers {
  public static int findSumOfPathNumbers(TreeNode root) {
    return findRootToLeafPathNumbers(root, 0);
  }

  private static int findRootToLeafPathNumbers(TreeNode currentNode, int pathSum) {
    if (currentNode == null)
      return 0;

    // 计算当前节点的路径和calculate the path number of the current node
    pathSum = 10 * pathSum + currentNode.val;

    // 如果当前节点是叶子结点，返回路径和
    if (currentNode.left == null && currentNode.right == null) {
      return pathSum;
    }

    // 遍历左右子树
    return findRootToLeafPathNumbers(currentNode.left, pathSum) +
           findRootToLeafPathNumbers(currentNode.right, pathSum);
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(0);
    root.right = new TreeNode(1);
    root.left.left = new TreeNode(1);
    root.right.left = new TreeNode(6);
    root.right.right = new TreeNode(5);
    System.out.println("Total Sum of Path Numbers: " + SumOfPathNumbers.findSumOfPathNumbers(root));
  }
}

JavaScript

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

class SumOfPathNumbers {
  static findSumOfPathNumbers(root) {
    return SumOfPathNumbers.findRootToLeafPathNumbers(root, 0);
  }

  static findRootToLeafPathNumbers(currentNode, pathSum) {
    if (currentNode === null) {
      return 0;
    }

    // 计算当前节点的路径和 calculate the path number of the current node
    pathSum = 10 * pathSum + currentNode.val;

    // 如果当前节点是叶子结点，返回路径和
    if (currentNode.left === null && currentNode.right === null) {
      return pathSum;
    }

    // 遍历左右子树
    return (
      SumOfPathNumbers.findRootToLeafPathNumbers(currentNode.left, pathSum) +
      SumOfPathNumbers.findRootToLeafPathNumbers(currentNode.right, pathSum)
    );
  }
}

const root = new TreeNode(1);
root.left = new TreeNode(0);
root.right = new TreeNode(1);
root.left.left = new TreeNode(1);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(5);
console.log("Total Sum of Path Numbers: " + SumOfPathNumbers.findSumOfPathNumbers(root));

Python

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


class SumOfPathNumbers:
    @staticmethod
    def findSumOfPathNumbers(root):
        return SumOfPathNumbers.findRootToLeafPathNumbers(root, 0)

    @staticmethod
    def findRootToLeafPathNumbers(currentNode, pathSum):
        if currentNode is None:
            return 0

        # 计算当前节点的路径和 calculate the path number of the current node
        pathSum = 10 * pathSum + currentNode.val

        # 如果当前节点是叶子结点，返回路径和
        if currentNode.left is None and currentNode.right is None:
            return pathSum

        # 遍历左右子树
        return (
            SumOfPathNumbers.findRootToLeafPathNumbers(currentNode.left, pathSum)
            + SumOfPathNumbers.findRootToLeafPathNumbers(currentNode.right, pathSum)
        )


root = TreeNode(1)
root.left = TreeNode(0)
root.right = TreeNode(1)
root.left.left = TreeNode(1)
root.right.left = TreeNode(6)
root.right.right = TreeNode(5)
print("Total Sum of Path Numbers:", SumOfPathNumbers.findSumOfPathNumbers(root))

Go

package main

import (
	"fmt"
)

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

func findSumOfPathNumbers(root *TreeNode) int {
	return findRootToLeafPathNumbers(root, 0)
}

func findRootToLeafPathNumbers(currentNode *TreeNode, pathSum int) int {
	if currentNode == nil {
		return 0
	}

	// 计算当前节点的路径和 calculate the path number of the current node
	pathSum = 10*pathSum + currentNode.val

	// 如果当前节点是叶子结点，返回路径和
	if currentNode.left == nil && currentNode.right == nil {
		return pathSum
	}

	// 遍历左右子树
	return findRootToLeafPathNumbers(currentNode.left, pathSum) +
		findRootToLeafPathNumbers(currentNode.right, pathSum)
}

func main() {
	root := &TreeNode{val: 1}
	root.left = &TreeNode{val: 0}
	root.right = &TreeNode{val: 1}
	root.left.left = &TreeNode{val: 1}
	root.right.left = &TreeNode{val: 6}
	root.right.right = &TreeNode{val: 5}
	fmt.Println("Total Sum of Path Numbers:", findSumOfPathNumbers(root))
}