Leetcode——树的子结构(子树)

1. 题目

2. 题解

符合树的子结构包含以下三种情况：

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

/*** 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) {if(A == null || B == null)return false;//答案默认为false，先判断 以节点 A 为根节点的子树 是否包含树 Bboolean res = false;res = dfs(A, B);if(res == true)return res;// 树B是树A左子树 的子结构，对应 isSubStructure(A.left, B)；// 树B是树A右子树 的子结构，对应 isSubStructure(A.right, B)；res = isSubStructure(A.left, B) || isSubStructure(A.right, B);return res;}/*终止条件：当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true；当节点 A 为空：说明已经越过树 A 的叶节点，即匹配失败，返回 false；当节点 A 和 B 的值不同：说明匹配失败，返回 false ；*/// 递归从当前节点开始，B是否为A的子树public boolean dfs(TreeNode A, TreeNode B){if(B == null)return true;        //子树B遍历到最后的叶子节点if(A == null)return false;       //已经越过A的叶子节点return (A.val == B.val && dfs(A.left, B.left) && dfs(A.right, B.right));}
}