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.

 [暴力解法]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

1. 两个点直接相等是两棵树相等的特殊情况，下次注意

［思维问题］：

只会写判断树的思路，不知道还有判断点的步骤, 二者需要分开

［一句话思路］：

判断树和判断点分开

［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

1. 布尔型函数必须有不在括号中的默认值，注意下
2. 调用点的traverse也是用的递归

［二刷］：

［三刷］：

［四刷］：

［五刷］：

  [五分钟肉眼debug的结果]：

［总结］：

1. 调用点的traverse也是用的递归

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［关键模板化代码］：

判断点是否相等：必须要左右都相等才行

public boolean isSame(TreeNode s, TreeNode t) {//both nullif (s == null && t == null) {return true;}//one is nullif (s == null || t == null) {return false;}//falseif (s.val != t.val) {return false;}//defaultreturn isSame(s.left, t.left) && isSame(s.right, t.right);}

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

 [代码风格] ：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public boolean isSubtree(TreeNode s, TreeNode t) {//corner caseif (s == null) {return false;}if (isSame(s,t)) {return true;}return isSubtree(s.left, t) || isSubtree(s.right, t);}public boolean isSame(TreeNode s, TreeNode t) {//both nullif (s == null && t == null) {return true;}//one is nullif (s == null || t == null) {return false;}//falseif (s.val != t.val) {return false;}//defaultreturn isSame(s.left, t.left) && isSame(s.right, t.right);}
}

转载于:https://www.cnblogs.com/immiao0319/p/8592222.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！