572. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:

Given tree s:

     3
    / \
   4   5
  / \
 1   2
Given tree t:
   4 
  / \
 1   2
Return true, because t has the same structure and node values with a subtree of s.

Example 2:\

Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
Given tree t:
   4
  / \
 1   2
Return false.

Hint:

1. Which approach is better here- recursive or iterative?
2. If recursive approach is better, can you write recursive function with its parameters?
3. Two trees s and t are said to be identical if their root values are same and their left and right subtrees are identical. Can you write this in form of recursive formulae?
4. Recursive formulae can be: isIdentical(s,t)= s.val==t.val AND isIdentical(s.left,t.left) AND isIdentical(s.right,t.right)

方法1: recursive + iterative

思路：

中序遍历s，把每一个判断每一个t节点是否和t成为same tree。

/**
 * 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:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        stack<TreeNode*> st;
        TreeNode* root = s;
        while (true) {
            if (root) {
                st.push(root);
                root = root -> left;
            }
            else {
                if (st.empty()) break;
                root = st.top();
                st.pop();
                
                if (isSame(root, t)) return true;
                root = root -> right;
            }
        }
        return false;
    }
    
    bool isSame(TreeNode* s, TreeNode* t) {
        if (!s && !t) return true;
        if (s && t) return (s -> val == t -> val) && isSame(s -> left, t -> left) && isSame(s -> right, t -> right);
        return false;
    }
};

用recursive的方法解决s的遍历也可以：

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (isSame(s, t)) return true;
        if (!s && !t) return true;
        if (s) {
            return isSubtree(s -> left, t) || isSubtree(s -> right, t);
        }
        return false;
    }
    
    bool isSame(TreeNode* s, TreeNode* t) {
        if (!s && !t) return true;
        if (s && t) return (s -> val == t -> val) && isSame(s -> left, t -> left) && isSame(s -> right, t -> right);
        return false;
    }
};