算法题/树的DFS：二叉树路径之和

题目

给定一棵二叉树和一个数字S，找出这棵树是否有一条从根到叶的路径，使该路径上所有节点值的和等于S。

解答

Java

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

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

class TreePathSum {
  public static boolean hasPath(TreeNode root, int sum) {
    if (root == null)
      return false;

    //如果当前节点是叶子结点并且它的值等于和sum，那么我们便找到了一条路径和等于sum
    if (root.val == sum && root.left == null && root.right == null)
      return true;

    // 递归调用左子树和右子树
    // 如果左右子树的任一子树返回true，那么将返回true
    return hasPath(root.left, sum - root.val) || hasPath(root.right, sum - root.val);
  }

  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(9);
    root.right.left = new TreeNode(10);
    root.right.right = new TreeNode(5);
    System.out.println("Tree has path: " + TreePathSum.hasPath(root, 23));
    System.out.println("Tree has path: " + TreePathSum.hasPath(root, 16));
  }
}

JavaScript

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

class TreePathSum {
  static hasPath(root, sum) {
    if (root === null) {
      return false;
    }

    if (root.val === sum && root.left === null && root.right === null) {
      return true;
    }

    return (
      TreePathSum.hasPath(root.left, sum - root.val) ||
      TreePathSum.hasPath(root.right, sum - root.val)
    );
  }
}

const root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(1);
root.left.left = new TreeNode(9);
root.right.left = new TreeNode(10);
root.right.right = new TreeNode(5);

console.log("Tree has path: " + TreePathSum.hasPath(root, 23));
console.log("Tree has path: " + TreePathSum.hasPath(root, 16));

Python

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


class TreePathSum:
    @staticmethod
    def hasPath(root, sum):
        if root is None:
            return False

        if root.val == sum and root.left is None and root.right is None:
            return True

        return (
            TreePathSum.hasPath(root.left, sum - root.val) or
            TreePathSum.hasPath(root.right, sum - root.val)
        )


root = TreeNode(12)
root.left = TreeNode(7)
root.right = TreeNode(1)
root.left.left = TreeNode(9)
root.right.left = TreeNode(10)
root.right.right = TreeNode(5)

print("Tree has path:", TreePathSum.hasPath(root, 23))
print("Tree has path:", TreePathSum.hasPath(root, 16))

Go

package main

import "fmt"

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

func hasPath(root *TreeNode, sum int) bool {
	if root == nil {
		return false
	}

	if root.val == sum && root.left == nil && root.right == nil {
		return true
	}

	return hasPath(root.left, sum-root.val) || hasPath(root.right, sum-root.val)
}

func main() {
	root := &TreeNode{val: 12}
	root.left = &TreeNode{val: 7}
	root.right = &TreeNode{val: 1}
	root.left.left = &TreeNode{val: 9}
	root.right.left = &TreeNode{val: 10}
	root.right.right = &TreeNode{val: 5}

	fmt.Println("Tree has path:", hasPath(root, 23))
	fmt.Println("Tree has path:", hasPath(root, 16))
}