链接
https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
难度： #中等
题目
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：
0 <= 节点个数 <= 10000
代码框架
/**
* 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) {
}
}
题目解析
1.创建一个辅助函数判断两棵树是否相等
2.递归遍历A树的每一个节点作为根结点和B树进行比较
3.每次遇到A的节点与B的头结点相同，则继续比较A和B的子节点
解答思路1：
在二叉树A中先序遍历，
找到第一个和B的第一个相同的节点，
然后比较其左右子节点是否相同，
如果B没有左或者右节点，则无需比较，
直接返回true,
如果A没有子节点，B有子节点，则一定不是，
直接返回false。
解答思路2：
解答思路1的代码优化写法，
利用了&&和||逻辑运算符的快速返回特性，
在二叉树A中先序遍历，
找到第一个和B的第一个相同的节点，
然后比较其左右子节点是否相同，
如果B没有左或者有节点，则无需比较。
测试用例
package edu.yuwen.sowrd.num26.solution;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import edu.yuwen.sowrd.entity.TreeNode;
import edu.yuwen.sowrd.num26.sol1.Solution;
public class SolutionTest {
/**
* 示例 1：
* 输入：A = [1,2,3], B = [3,1]
* 输出：false
*/
@Test
public void testCase1() {
Solution solution = new Solution();
TreeNode a = getTreeNodeA1();
TreeNode b = getTreeNodeB1();
boolean res = solution.isSubStructure(a, b);
Assertions.assertEquals(false, res);
}
/**
* 示例 2：
* 输入：A = [3,4,5,1,2], B = [4,1]
* 输出：true
*/
@Test
public void testCase2() {
Solution solution = new Solution();
TreeNode a = getTreeNodeA2();
TreeNode b = getTreeNodeB2();
boolean res = solution.isSubStructure(a, b);
Assertions.assertEquals(true, res);
}
/**
* 1
* / \
* 2 3
*/
public TreeNode getTreeNodeA1() {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
node1.left = node2;
node1.right = node3;
return node1;
}
/**
* 3
* /
* 1
*/
public TreeNode getTreeNodeB1() {
TreeNode node1 = new TreeNode(3);
TreeNode node2 = new TreeNode(1);
node1.left = node2;
return node1;
}
/**
* 3
* / \
* 4 5
* / \
* 1 2
*/
public TreeNode getTreeNodeA2() {
TreeNode node1 = new TreeNode(3);
TreeNode node2 = new TreeNode(4);
TreeNode node3 = new TreeNode(5);
TreeNode node4 = new TreeNode(1);
TreeNode node5 = new TreeNode(2);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
return node1;
}
/**
* 4
* /
* 1
*/
public TreeNode getTreeNodeB2() {
TreeNode node1 = new TreeNode(4);
TreeNode node2 = new TreeNode(1);
node1.left = node2;
return node1;
}
}
解答1
package edu.yuwen.sowrd.num26.sol1;
import edu.yuwen.sowrd.entity.TreeNode;
public class Solution {
public boolean isSubStructure(TreeNode a, TreeNode b) {
if (a == null || b == null) {
return false;
}
// 比较当前节点及其子节点
boolean cur = compare(a, b);
// 确定是子结构即可返回
if (cur) {
return true;
}
// 否则遍历左右子树
if (a.left != null) {
boolean left = isSubStructure(a.left, b);
// 只要相等了，即可返回
if (left) {
return true;
}
}
if (a.right != null) {
boolean right = isSubStructure(a.right, b);
if (right) {
return true;
}
}
return false;
}
// 比较两颗二叉树是否相同
private boolean compare(TreeNode a, TreeNode b) {
// base case
if (a == null) {
if (b == null) {
return true;
}
return false;
}
if (a != null && b == null) {
return true;
}
// 比较当前值
boolean cur = a.val == b.val;
// 只要有一个节点不同，即可返回
if (!cur) {
return false;
}
// 比较左节点
boolean left = compare(a.left, b.left);
if (!left) {
return false;
}
// 比较右节点
boolean right = compare(a.right, b.right);
if (!right) {
return false;
}
// 当前和左右节点都相同，才认为相同
return true;
}
}
解答2 推荐
package edu.yuwen.sowrd.num26.sol2;
import edu.yuwen.sowrd.entity.TreeNode;
public class Solution {
public boolean isSubStructure(TreeNode a, TreeNode b) {
if (a == null || b == null) {
return false;
}
// 先序遍历二叉树A， 比较当前节点及其子节点
// 确定是子结构即可返回
// 否则遍历二叉树a下一个节点
return compare(a, b) || isSubStructure(a.left, b)
|| isSubStructure(a.right, b);
}
// 比较两颗二叉树是否相同
private boolean compare(TreeNode a, TreeNode b) {
// base case
// b为null,则一定相同
if (b == null) {
return true;
}
// b不为null，但a为null,则一定不同
else if (a == null) {
return false;
}
// 比较当前值, 比较左节点,比较右节点
// 当前和左右节点都相同，才认为相同
// 否则只要有一个节点不同，即可返回
return a.val == b.val && compare(a.left, b.left)
&& compare(a.right, b.right);
}
}
网友评论