算法题/树的DFS：给定序列的路径

题目

给定一棵二叉树和一个数字序列，找出该序列在给定的树中是否作为根到叶的路径出现。

解答

Java

import java.util.*;

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

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

class PathWithGivenSequence {
  public static boolean findPath(TreeNode root, int[] sequence) {
    if (root == null)
      return sequence.length == 0;

    return findPathRecursive(root, sequence, 0);
  }

  private static boolean findPathRecursive(TreeNode currentNode, int[] sequence, int sequenceIndex) {

    if (currentNode == null)
      return false;

    if (sequenceIndex >= sequence.length || currentNode.val != sequence[sequenceIndex])
      return false;

    // 如果当前节点是一个叶子结点，添加它到序列的末尾
    if (currentNode.left == null && currentNode.right == null && sequenceIndex == sequence.length - 1)
      return true;

    // 递归调用左子树和右子树
    // 如果左右子树的任一子树返回true，那么将返回true
    return findPathRecursive(currentNode.left, sequence, sequenceIndex + 1)
        || findPathRecursive(currentNode.right, sequence, sequenceIndex + 1);
  }

  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("Tree has path sequence: " + PathWithGivenSequence.findPath(root, new int[] { 1, 0, 7 }));
    System.out.println("Tree has path sequence: " + PathWithGivenSequence.findPath(root, new int[] { 1, 1, 6 }));
  }
}

JavaScript

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

class PathWithGivenSequence {
  static findPath(root, sequence) {
    if (root === null)
      return sequence.length === 0;

    return PathWithGivenSequence.findPathRecursive(root, sequence, 0);
  }

  static findPathRecursive(currentNode, sequence, sequenceIndex) {
    if (currentNode === null)
      return false;

    if (sequenceIndex >= sequence.length || currentNode.val !== sequence[sequenceIndex])
      return false;

    if (currentNode.left === null && currentNode.right === null && sequenceIndex === sequence.length - 1)
      return true;

    return PathWithGivenSequence.findPathRecursive(currentNode.left, sequence, sequenceIndex + 1)
      || PathWithGivenSequence.findPathRecursive(currentNode.right, sequence, sequenceIndex + 1);
  }
}

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("Tree has path sequence: " + PathWithGivenSequence.findPath(root, [1, 0, 7]));
console.log("Tree has path sequence: " + PathWithGivenSequence.findPath(root, [1, 1, 6]));

Python

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

class PathWithGivenSequence:
    @staticmethod
    def findPath(root, sequence):
        if root is None:
            return len(sequence) == 0

        return PathWithGivenSequence.findPathRecursive(root, sequence, 0)

    @staticmethod
    def findPathRecursive(currentNode, sequence, sequenceIndex):
        if currentNode is None:
            return False

        if sequenceIndex >= len(sequence) or currentNode.val != sequence[sequenceIndex]:
            return False

        if currentNode.left is None and currentNode.right is None and sequenceIndex == len(sequence) - 1:
            return True

        return PathWithGivenSequence.findPathRecursive(currentNode.left, sequence, sequenceIndex + 1) \
            or PathWithGivenSequence.findPathRecursive(currentNode.right, sequence, sequenceIndex + 1)

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("Tree has path sequence:", PathWithGivenSequence.findPath(root, [1, 0, 7]))
print("Tree has path sequence:", PathWithGivenSequence.findPath(root, [1, 1, 6]))

Go

package main

import "fmt"

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

type PathWithGivenSequence struct{}

func (p *PathWithGivenSequence) findPath(root *TreeNode, sequence []int) bool {
	if root == nil {
		return len(sequence) == 0
	}

	return p.findPathRecursive(root, sequence, 0)
}

func (p *PathWithGivenSequence) findPathRecursive(currentNode *TreeNode, sequence []int, sequenceIndex int) bool {
	if currentNode == nil {
		return false
	}

	if sequenceIndex >= len(sequence) || currentNode.val != sequence[sequenceIndex] {
		return false
	}

	if currentNode.left == nil && currentNode.right == nil && sequenceIndex == len(sequence)-1 {
		return true
	}

	return p.findPathRecursive(currentNode.left, sequence, sequenceIndex+1) ||
		p.findPathRecursive(currentNode.right, sequence, sequenceIndex+1)
}

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}

	p := PathWithGivenSequence{}
	fmt.Println("Tree has path sequence:", p.findPath(root, []int{1, 0, 7}))
	fmt.Println("Tree has path sequence:", p.findPath(root, []int{1, 1, 6}))
}