Lstmxx的空间

1367. 二叉树中的列表

给你一棵以  root  为根的二叉树和一个  head  为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以  head  为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

链接

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @param {TreeNode} root
 * @return {boolean}
 */

function same(node, head) {
  if (node === null) {
    return head === null;
  }
  if (head === null) return true;
  return (
    node.val === head.val &&
    (same(node.left, head.next) || same(node.right, head.next))
  );
}

var isSubPath = function (head, root) {
  function dfs(node) {
    if (node === null) {
      return false;
    }

    const lr = dfs(node.left);
    const rl = dfs(node.right);

    return same(node, head) || lr || rl;
  }

  return dfs(root);
};