树的子结构
题目描述
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
思路
1.递归比较两个树的结构。
2.比较A树和B树当前的结点,若A树和B树的值相等,则继续比较它们的左右子树;若不相等,则拿A树的左子树和右子树分别进行同样的比较。
3.当B树遍历到了空结点,说明B是A的子结构;否则不是A的子结构。
Java代码实现
public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root1 == null || root2 == null){ return false; } boolean flag = judge(root1,root2); if(!flag){ flag = HasSubtree(root1.left,root2); } if(!flag){ flag = HasSubtree(root1.right,root2); } return flag; } private boolean judge(TreeNode root1,TreeNode root2){ if(root2 == null) return true; if(root1 == null) return false; if(root1.val != root2.val) return false; return judge(root1.left,root2.left)&&judge(root1.right,root2.right); }
Golang代码实现
func HasSubtree(s *TreeNode, t *TreeNode) bool { if s == nil || t == nil{ return false } flag := judgeTree(s,t) if !flag{ flag = HasSubtree(s.Left,t) } if !flag{ flag = HasSubtree(s.Right,t) } return flag } func judge(s *TreeNode, t *TreeNode) bool { if t == nil{ return true } if s == nil && t != nil{ return false } if s != nil && t == nil{ return false } if s.Val != t.Val { return false } return judge(s.Left,t.Left) && judge(s.Right,t.Right) }