树的子结构（入门算法15）——深度优先遍历

本文主要是介绍树的子结构（入门算法15）——深度优先遍历，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:

给定的树 B：

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

实例：

输入：A = [1,2,3], B = [3,1]
输出：false

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

解题思路：
1、首先判断B树，如果B是空树的话，那么直接就返回false。
2、如果B不是空树，那么我们遍历A树，找到A树中所有等于B根节点的节点。保存到subTrees 链表中。
3、遍历subTrees链表的每个节点。根据B的结构判断A的子树是否也有相同的结构（如果B有左孩子，那么判断B的左孩子是否等于A的子树的左孩子，如果B有右孩子，那么判断B的右孩子是否等于A的子树的右孩子），经过一番深度优先算法的遍历后，如果是那么返回true，如果不是，那么返回false。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //判断B是不是空树
        if(B == null){
            return false;
        }
        //存放所有跟B节点值相同的A节点
        LinkedList<TreeNode> subTrees = new LinkedList<TreeNode>();

        //遍历A树，找出所有等于B的根的值的节点。
        subTrees = findRoot(subTrees, A ,B.val);

        //非空表示找到了A树中B树的根节点
        if(subTrees.size() != 0){
            //遍历每个等于B根节点的节点
            for(int i = 0; i < subTrees.size(); i++){
                if(queryTree(subTrees.get(i),B) == true)     return true;
            }
        }
        return false;
    }

    //递归，深度遍历A树，找出所有等于B的根的值的节点。
    public LinkedList<TreeNode> findRoot(LinkedList subTrees,TreeNode A, int target){
        if(A.val == target){
            subTrees.add(A);
        }
        if(A.left != null){
            findRoot(subTrees, A.left, target);
        }
        if(A.right != null){
            findRoot(subTrees, A.right, target);
        }
        return subTrees;
    }

    //递归,深度遍历B树是否和A树的子结构重合
    public boolean queryTree(TreeNode subTree, TreeNode B){
        if(subTree.val == B.val){
            boolean left = true;
            boolean right = true;
            //A的左右子树先为空，那么B不是A的子结构
            if(subTree.left == null && B.left != null)    return false;
            if(subTree.right == null && B.right != null)  return false;

            if(B.left != null && subTree.left != null){
                left = queryTree(subTree.left, B.left);
            }
            if(B.right != null && subTree.right != null){
                right = queryTree(subTree.right, B.right);
            }
            if(left && right)   return true;
            if(B.left == null && B.right == null){
                return true;
            }
        }
        return false;
    }
}

力扣战绩：

我们再看看大牛的写法：
解题思路：
1、当 树 A 为空 或 树 B 为空 时，直接返回 false；
2、 若树 B 是树 A 的子结构，则必满足以下三种情况之一：

1. 以 节点 A 为根节点的子树 包含树 B ，对应 recur(A, B)；
2. 树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)；
3. 树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)；

3、recur(A, B) 函数：

1. 判断 A 和 B 的左子节点是否相等，即 recur(A.left, B.left) ；
2. 判断 A 和 B 的右子节点是否相等，即 recur(A.right, B.right) ；
3. 终止条件：
   当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true ；
   当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false ；
   当节点 A 和 B 的值不同：说明匹配失败，返回 false ；

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

力扣战绩：（这种用更少行代码写出比自己快而且内存消耗更少的代码。。。。哎，无话可说）

这篇关于树的子结构（入门算法15）——深度优先遍历的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！