1367. Linked List in Binary Tree

Given a binary tree root and a linked list with head as the first node. 

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.  

Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

• 1 <= node.val <= 100 for each node in the linked list and binary tree.
• The given linked list will contain between 1 and 100 nodes.
• The given binary tree will contain between 1 and 2500 nodes.

---

给定一棵二叉树和一个链表，问链表中的元素是否是二叉树中某一条向下的路径的一部分，结合题中的例子，很容易理解题意。

我的做法是，对于链表head和二叉树root，首先在root中找到所有值是head的节点，也就是找到树中的开始比对的节点。然后，链表中的节点和树中的节点递归比对，直到走完链表比对成功，或者出现不相等或树没有孩子节点，比对失败。

完整代码如下：

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

 //Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
 
//Definition for a binary tree node.
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
  
class Solution {
public:
	void findStartNodes(vector<TreeNode*> &starts, TreeNode* root, int val) {
		if (root->val == val)starts.push_back(root);
		if (root->left != NULL)findStartNodes(starts, root->left, val);
		if (root->right != NULL)findStartNodes(starts, root->right, val);
	}

	bool findSubPath(ListNode* head, TreeNode* root) {
		if (head->next == NULL) {
			return true;
		}
		else {
			bool left_ans = false, right_ans = false;
			if (root->left != NULL && root->left->val == head->next->val) {
				left_ans =  findSubPath(head->next, root->left);
			}
			if (root->right != NULL && root->right->val == head->next->val) {
				right_ans = findSubPath(head->next, root->right);
			}
			return left_ans || right_ans;
		}
	}

	bool isSubPath(ListNode* head, TreeNode* root) {
		vector<TreeNode*> starts;
		findStartNodes(starts, root, head->val);

		for (int i = 0; i < starts.size(); ++i) {
			if (findSubPath(head, starts[i]))return true;
		}

		return false;
	}
};

ListNode* genList(const vector<int> &vec) {
	if (vec.size() == 0)return NULL;
	ListNode* head = new ListNode(vec[0]);
	ListNode* cur = head;
	for (int i = 1; i < vec.size(); ++i) {
		ListNode* node = new ListNode(vec[i]);
		cur->next = node;
		cur = node;
	}
	return head;
}

// -1表示空节点
TreeNode* genTree(const vector<int> &vec) {
	if (vec.size() == 0)return NULL;

	vector<TreeNode*> nodes(vec.size(), NULL);
	for (int i = 0; i < vec.size(); ++i) {
		if (vec[i] != -1) {
			nodes[i] = new TreeNode(vec[i]);
		}
	}
	
	int npar = 0, nchild = 1;
	while (true) {
		if (nchild >= nodes.size())break;

		int nnextpar = nchild;
		while (npar < nnextpar) {
			if (nodes[npar] != NULL) {
				if (nchild >= nodes.size())break;
				nodes[npar]->left = nodes[nchild++];
				if (nchild >= nodes.size())break;
				nodes[npar]->right = nodes[nchild++];
			}
			++npar;
		}
		npar = nnextpar;
	}
	
	return nodes[0];
}


int main() {
	vector<int> vec = { 1,4,4,-1,2,2,-1,1,-1,6,8,-1,-1,-1,-1,1,3 };
	TreeNode* root = genTree(vec);

	vector<int> vec2 = { 1,4,2,6,8 };
	ListNode* head = genList(vec2);

	Solution s;
	bool ans = s.isSubPath(head, root);
	return 0;
}

本代码提交AC，用时36MS。

之前在LeetCode Minimum Depth of Binary Tree中我曾写过一个genTree的辅助函数，根据数组生成对应的二叉树。但是那个函数要求二叉树是完全二叉树，如果二叉树残缺很多节点的话，构造数组很麻烦。比如用之前的函数构造此题示例的二叉树，则数组中需要添加很多-1，很麻烦而且容易出错。

借此题的机会，我重写了一个genTree的辅助函数，如上代码所示。这个构造函数方便很多，对于输入数组，每个节点的左右孩子依次追加在数组的后面，也不用为空节点的孩子保留-1。genTree的时候先构造好所有节点，然后根据规则把这些节点连接起来。具体使用方法可以看代码中的示例。