剑指offer-17、树的⼦结构
<h2 id="题描述">题⽬描述</h2><p>输⼊两棵⼆叉树A ， B ，判断B 是不是A 的⼦结构。（ps：我们约定空树不是任意⼀个树的⼦结构）</p>
<p>假如给定A 为{8,8,7,9,2,#,#,#,#,4,7} ， B 为{8,9,2} ， 2 个树的结构如下，可以看出B是A 的⼦结构:</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503291233833.png" alt="" loading="lazy"></p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="双重递归法标准解法">双重递归法（标准解法）</h3>
<p>使用两个递归函数：</p>
<ol>
<li><code>isSubStructure</code>：遍历树A的每个节点，寻找与树B根节点值相同的节点</li>
<li><code>recur</code>：从匹配的节点开始，递归比较两棵树的对应节点是否相同</li>
</ol>
<pre><code class="language-java">public class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
// 空树不是任何树的子结构
if (A == null || B == null) return false;
// 三种情况满足一种即可：
// 1. B是以A为根的子结构
// 2. B是A左子树的子结构
// 3. B是A右子树的子结构
return hasSubtree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
// 判断B是否是A的子结构（从当前节点开始）
private boolean hasSubtree(TreeNode A, TreeNode B) {
// B已经遍历完，说明匹配成功
if (B == null) return true;
// A遍历完但B还有节点，或节点值不匹配
if (A == null || A.val != B.val) return false;
// 递归比较左右子树
return hasSubtree(A.left, B.left) && hasSubtree(A.right, B.right);
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(mn)，m和n分别是树A和树B的节点数</li>
<li><strong>空间复杂度</strong>：O(m)，递归栈的深度最大为树A的高度</li>
</ul>
<h3 id="迭代递归混合法">迭代+递归混合法</h3>
<ol>
<li>使用迭代法（栈或队列）遍历树A</li>
<li>当找到与树B根节点值相同的节点时，切换到递归比较</li>
<li>结合了迭代和递归的优点</li>
</ol>
<pre><code class="language-java">public class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null) return false;
Stack<TreeNode> stack = new Stack<>();
stack.push(A);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
// 找到匹配的根节点，开始递归比较
if (node.val == B.val && compareTrees(node, B)) {
return true;
}
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return false;
}
private boolean compareTrees(TreeNode A, TreeNode B) {
if (B == null) return true;
if (A == null || A.val != B.val) return false;
return compareTrees(A.left, B.left) && compareTrees(A.right, B.right);
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(mn)</li>
<li><strong>空间复杂度</strong>：O(m)，栈的空间消耗</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19006428
頁:
[1]