剑指offer：树的子结构

妖狐艹你老母 2021-09-16 16:26 305阅读 0赞

**试题：**  
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）  
**代码：**  
按照正常思维，我们都知道要一个个搜搜树的节点，每到一个节点，就和树B比较一次。因此  
我们使用深度搜索来搜索树的每个节点。首先我们假设B和A都非null，这时我们可以写出递归遍历，因为每到下一个A节点，问题就又变成原始问题了。然后我们考虑递归终止条件，显然只要遍历到当前节点为null就可以返回了（该路径搜索完成，应该返回false）。那么该如何返回是个问题，因为我们只需要找到一个满足条件就可以返回，因此最终形式以||的关系。然后只需要把A或B等于null的边界条件加进去。  
然后我们考虑如何比较子树，显然这又是个递归问题。只要当前节点值相等我们就可以继续比较下一节点，由于所有节点都要满足相等，所以以&&的形式返回。然后就是终止条件的考虑。当我们遍历到B的叶子节点时，当其为null，我们可以对当前路径返回true，如果不为null，则有两种可能性，要不可以继续比较，要不A下一节点为null了  
[BFS广度优先搜索 DFS深度优先搜索 回溯算法][BFS_ DFS_]

/**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        private boolean isSubTree(TreeNode root1,TreeNode root2) {
            if(root2==null) return true;
            if(root1==null) return false;
            if(root1.val == root2.val){
                return isSubTree(root1.left,root2.left) && isSubTree(root1.right,root2.right);
            }else return false;
        }
        public boolean HasSubtree(TreeNode root1,TreeNode root2) {
            if(root1==null || root2==null) return false;
            return isSubTree(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
        }
    }

[BFS_ DFS_]: https://blog.csdn.net/qq_16234613/article/details/77384096