Checking Subtree of Another Tree using Preorder Traversal or Rec

  • 时间:2020-09-19 10:45:07
  • 分类:网络文摘
  • 阅读:94 次

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.

Hints:

  • Which approach is better here- recursive or iterative?
  • If recursive approach is better, can you write recursive function with its parameters?
  • 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?
  • Recursive formulae can be: isIdentical(s,t)= s.val==t.val AND isIdentical(s.left,t.left) AND isIdentical(s.right,t.right)

Checking Subtree using Binary Tree Preorder Traversal

If a binary tree is the subtree of another binary tree, then its preorder traversal sequence string must be the substring of another one’s. Thus, we just need to use the recursion to obtained the binary tree preorder traversal and compare both preorder strings.

For a precise preorder traversal, we can distinguish the left and right nodes, therefore, we can pass a boolean parameter to denote whether current node is in the left or the right branch.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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) {
        string tree1 = preorder(s, true);
        string tree2 = preorder(t, true);
        return tree1.find(tree2) != string::npos;
    }
    
private:
    string preorder(TreeNode* t, bool left) {
        if (t == nullptr) {
            if (left) {
                return "lnull";
            }
            return "rnull";
        }
        return "#" + std::to_string(t->val) + " " +
            preorder(t->left, true) + " " +
            preorder(t->right, false);
    }
};
/**
 * 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) {
        string tree1 = preorder(s, true);
        string tree2 = preorder(t, true);
        return tree1.find(tree2) != string::npos;
    }
    
private:
    string preorder(TreeNode* t, bool left) {
        if (t == nullptr) {
            if (left) {
                return "lnull";
            }
            return "rnull";
        }
        return "#" + std::to_string(t->val) + " " +
            preorder(t->left, true) + " " +
            preorder(t->right, false);
    }
};

However, this is not entirely necessary, and we can simplify the implementation a bit as the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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) {
        string tree1 = preorder(s);
        string tree2 = preorder(t);
        return tree1.find(tree2) != string::npos;
    }
    
private:
    string preorder(TreeNode* t) {
        if (t == nullptr) {
            return "null";
        }
        return "#" + std::to_string(t->val) + " " +
            preorder(t->left) + " " +
            preorder(t->right);
    }
};
/**
 * 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) {
        string tree1 = preorder(s);
        string tree2 = preorder(t);
        return tree1.find(tree2) != string::npos;
    }
    
private:
    string preorder(TreeNode* t) {
        if (t == nullptr) {
            return "null";
        }
        return "#" + std::to_string(t->val) + " " +
            preorder(t->left) + " " +
            preorder(t->right);
    }
};

Time complexity : O(m^2+n^2+m*n): A total of nn nodes of the tree ss and mm nodes of tree tt are traversed. Assuming string concatenation takes O(k) time for strings of length k and indexOf takes O(m*n).

Space complexity: O(max(m,n)). The depth of the recursion tree can go upto nn for tree t and m for tree s in worst case.

Recursive Checking using Same Tree Algorithm

We can compare the nodes of the both tree. We know that if both trees are identical, then one binary tree is the sub-tree of another. To check if both trees are identical, we can recursively check the current node value and its left and right branches.

Then, if a binary tree A is subtree of another B, it must be one of these: A equals B (same tree), A’s left is subtree of B (recursive check) or A’s right is subtree of B (recursive check).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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) {
        if (isSame(s, t)) return true;
        if (s == nullptr) return false;
        return 
            isSubtree(s->left, t) ||
            isSubtree(s->right, t);
    }
private:
    bool isSame(TreeNode* s, TreeNode * t) {
        if (s == nullptr && t == nullptr) {
            return true;
        }
        if (s == nullptr || t == nullptr) {
            return false;
        }
        return (s->val == t->val) && 
                isSame(s->left, t->left) && 
                isSame(s->right, t->right);
    }
};
/**
 * 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) {
        if (isSame(s, t)) return true;
        if (s == nullptr) return false;
        return 
            isSubtree(s->left, t) ||
            isSubtree(s->right, t);
    }
private:
    bool isSame(TreeNode* s, TreeNode * t) {
        if (s == nullptr && t == nullptr) {
            return true;
        }
        if (s == nullptr || t == nullptr) {
            return false;
        }
        return (s->val == t->val) && 
                isSame(s->left, t->left) && 
                isSame(s->right, t->right);
    }
};

Time complexity : O(m*n). In worst case(skewed tree) traverse function takes O(m*n) time.
Space complexity : O(n). The depth of the recursion tree can go upto n. n refers to the number of nodes in s.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
为 WordPress 主题添加花瓣飘落特效  wordpress插件:WP-China-Yes 切换WP站点与官方通信至国内节点解决后台更新429错误  一段代码轻松解决wordpress定时发布失败的问题  WordPress官网打不开 出现 429 Too Many Request 的原因  下载更新wordpress程序及插件的方法  禁用wordpress4.4+版本自动生成768w像素缩略图功能  自动为wordpress文章图片添加alt属性和title属性  如何为WordPress导航菜单、标签、出站等链接添加nofollow标签属性  如何设置WordPress的RSS feed更新频率  利用WordPress开发者调试模式解决PHP500内部服务器错误 
评论列表
添加评论