LeetCode 1367. 二叉树中的列表(二叉树的遍历、DFS)

二叉树中的列表
时间一般
先遍历二叉树，找到所有起点;
然后对于每个起点搜寻是否存在这样的路径。

/**
 * 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:
    queue<TreeNode*> startNodes;
    int start;
    bool isSubPath(ListNode* head, TreeNode* root) {
        start = head->val;
        getStartNodes(root);
        while(!startNodes.empty()){
            TreeNode* r = startNodes.front();
            startNodes.pop();
            if(dfs(r,head)){
                return true;
            }
        }
        return false;
    }

    bool dfs(TreeNode* root, ListNode* head){
        if(!head){
            return true;
        }
        if(head && !root){
            return false;
        }
        if(root->val == head->val){
            if(dfs(root->left,head->next)){
                return true;
            }
            if(dfs(root->right,head->next)){
                return true;
            }
        }
        return false;
    }


    void getStartNodes(TreeNode *root){
        if(!root){
            return ;
        }
        if(root->val==start){
            startNodes.push(root);
        }
        getStartNodes(root->left);
        getStartNodes(root->right);
    }
};