[leetcode] 572. Subtree of Another Tree

[leetcode] 572. Subtree of Another Tree

Description

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.

分析

题目的意思是：判断树t是否是树s的子树。

子树必须是叶结点开始的，中间某个部分的不能算是子树，那么是不是从s的某个节点开始，跟t的所有结构都一样，这个问题就转换成了判断两棵树是否相同，也就是Same Tree的问题了。我们先从s的根节点出发，跟t比较，如果两棵树完全相同，那么返回true，否则就分别对左子结点和右子结点调用递归来判断是否相同，只要一个返回true了，就表示可以找得到。

代码

/** * 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(!s){ return false; } if(isSame(s,t)){ return true; } return isSubtree(s->left,t)||isSubtree(s->right,t); } bool isSame(TreeNode* s, TreeNode* t){ if(!s&&!t){ return true; } if(!s||!t){ return false; } if(s->val!=t->val){ return false; } return isSame(s->left,t->left)&&isSame(s->right,t->right); }};

参考文献

​​[LeetCode] Subtree of Another Tree 另一个树的子树​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。