dedecms 旅游网站模板,wordpress可视化编辑主题,四川住房建设厅网站首页,网站制作有哪些种类1. 题目
输入两棵二叉树A和B#xff0c;判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构#xff0c; 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:3/ \4 5/ \1 2
给定的树 B#xff1a;4 /1
返回 true#xff0c;因为 B 与 A 的一…1. 题目
输入两棵二叉树A和B判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:3/ \4 5/ \1 2
给定的树 B4 /1
返回 true因为 B 与 A 的一个子树拥有相同的结构和节点值。示例 1
输入A [1,2,3], B [3,1]
输出false示例 2
输入A [3,4,5,1,2], B [4,1]
输出true限制
0 节点个数 10000来源力扣LeetCode 链接https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
遍历A每个节点值与 B 的 root 值相等的开启再次递归 check
class Solution {bool found false;
public:bool isSubStructure(TreeNode* A, TreeNode* B) {if(!A || !B) return false;if(A-val B-val){found check(A, B);if(found)return found;}isSubStructure(A-left,B);isSubStructure(A-right,B);return found;}bool check(TreeNode* A, TreeNode* B){if(found || !B || !A){if(found || !B)return true;return false;}if(A-val B-val){return (check(A-left,B-left)check(A-right,B-right));}return false;}
};优化return isSubStructure(A-left,B)||isSubStructure(A-right,B)可以剪枝找到后及时 return
class Solution {bool found false;
public:bool isSubStructure(TreeNode* A, TreeNode* B) {if(!A || !B) return false;if(A-val B-val){found check(A, B);if(found)return found;} return isSubStructure(A-left,B)||isSubStructure(A-right,B);}bool check(TreeNode* A, TreeNode* B){if(found || !B || !A){if(found || !B)return true;return false;}if(A-val B-val){return (check(A-left,B-left)check(A-right,B-right));}return false;}
};
