题目描述
给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例
给定的树 s: 3 / \ 4 5 / \ 1 2 给定的树 t: 4 / \ 1 2 返回 true,因为 t 与 s 的一个子树拥有相同的结构和节点值。
思路
1.递归比较两个数的结构。
2.比较A树和B树当前的结点,若A树和B树的值相等,则继续比较它们的左右子树;若不相等,则拿A树的左子树和右子树进行同样的过程。
3.当A树和B树同时遍历到了空结点,说明B是A的子结构;否则不是A的子结构。
Java代码实现
class Solution { public boolean isSubtree(TreeNode s, TreeNode t) { if(s == null && t != null){ return false; } boolean flag = judgeTree(s,t); if(!flag){ flag = isSubtree(s.left,t); } if(!flag){ flag = isSubtree(s.right,t); } return flag; } private boolean judgeTree(TreeNode s, TreeNode t){ if(s == null && t == null){ return true; } if(s != null && t == null){ return false; } if(s == null && t != null){ return false; } if(s.val != t.val){ return false; } return judgeTree(s.left,t.left) && judgeTree(s.right,t.right); } }
Golang代码实现
func isSubtree(s *TreeNode, t *TreeNode) bool { if s == nil && t != nil{ return false } flag := judgeTree(s,t) if !flag{ flag = isSubtree(s.Left,t) } if !flag{ flag = isSubtree(s.Right,t) } return flag } func judgeTree(s *TreeNode, t *TreeNode) bool { if s == nil && t != nil{ return false } if s != nil && t == nil{ return false } if s == nil && t == nil{ return true } if s.Val != t.Val { return false } return judgeTree(s.Left,t.Left) && judgeTree(s.Right,t.Right) }