来自剑指offer
这题有点难度,解题思想是:若B是A的子树,则子树的根节点可能为树A中的任意一个节点,因此只需要遍历树A的每个节点,判断以这个节点为根节点的树是否包含子树B,判断这个根节点是否包含子树B的方法是递归判断左右节点是否相等,若不相等则不包含子树B,若在判断的时候该根节点的树已经空了,而子树B不空,也表示不包含子树B,若子树B为空,则表明该根节点的树还有剩余的节点,包含了子树B,若两树均空,则表明刚好包含子树B。
下面代码使用层序遍历遍历树A的每个节点,使用isSub函数判断以当前节点为根节点的树是否包含子树B。
import javax.sound.midi.Soundbank;
import java.util.*;
public class Solution {
public boolean isSub(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 != null)
return false;
if (root2 == null)
return true;
if (root1 == null && root2 == null)
return true;
if (root1.val != root2.val)
return false;
return isSub(root1.left, root2.left) && isSub(root1.right, root2.right);
}
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if ((root1 == null) || (root2 == null))
return false;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root1);
while (queue.isEmpty() == false) {
TreeNode node = queue.poll();
if (node.val == root2.val) {
boolean result = isSub(node, root2);
if (result)
return true;
}
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
return false;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)