Leetcode : 0572. Subtree of Another Tree (Tree)

tags:leetcode

> DFS method
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(!root) return false;

        if(isSametree(root,subRoot)){ //if root same subRoot
            return true;
        }else{
            return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot); // check root->left and root->right.
        }
    }

    bool isSametree(TreeNode* root, TreeNode* subRoot){
        if(!root || !subRoot){//check below is same
            return root==NULL && subRoot==NULL;
        }else if(root->val == subRoot->val){ //check val.
            return isSametree(root->left,subRoot->left) && isSametree(root->right,subRoot->right);
        }else{
            return false;
        }
    }
};

Tip condtion
first , root ->left and right last is null ,euqal subRoot is true;
second , val equal val
third , if root not same , find next on root->left , root->right.