leetcode6-572. Subtree of Another Tree

1. problem

1. check if subRoot appear in root. (include all leaf)

2. init

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:

3. thought

1. no root check.
2. try match each node traversed
3. if match! return True (will stop traverse in that branch)
4. otherwise go on traversal.

4. trouble

1. 請善用卡條件 return

5.final solution

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # 1. no root check.
        # 2. try match each node traversed
        # 3. if match! return True (will stop traverse in that branch)
        # 4. otherwise go on traversal.
        if not root: return False
        if self.match(root, subRoot): return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
    def match(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]):
        # if both no more node for traversal, good.
        if not root and not subRoot: return True 
        # if one of them have node, the other not, bad. 
        if not root or not subRoot: return False
        # also check value are the same, and dig more.
        return ( root.val == subRoot.val) and self.match(root.left,subRoot.left)  and self.match(root.right,subRoot.right)

參考, C++ serialize

/**
 * 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) {
        ostringstream os1, os2;
        serialize(root, os1);
        serialize(subRoot, os2);
        return os1.str().find(os2.str()) != string::npos;
    }
    void serialize(TreeNode* node, ostringstream& os){
        if (!node) os << ",#";
        else {
            os << "," << node->val;
            serialize(node->left, os);
            serialize(node->right, os);
        }
    }
};