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

2021/10/19 1:09:28

本文主要是介绍树的子结构(入门算法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)——深度优先遍历的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程