树的子结构
1. 题目形容
输出两棵二叉树 A,B,判断 B 是不是 A 的子结构。(ps:咱们约定空树不是任意一个树的子结构)
2. 示例
无
3. 解题思路
波及树结构的题目,个别都应用递归办法
- 如果两棵二叉树 节点值不雷同:
1-1:递归遍历 A 树左子树
1-2:递归遍历 A 树右子树
- 如果两棵二叉树 节点值雷同:
1-1:B 树为空,则 B 是 A 的子树
1-2:递归判断 AB 树节点值是否雷同
4. Java 实现
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {this.val = val;}
}
*/
public class Solution {public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean res = false;
if (root1 != null && root2 != null){if (root1.val == root2.val){res = doseSubtree(root1, root2);
}
if (res == false){res = HasSubtree(root1.left, root2);
}
if (res == false){res = HasSubtree(root1.right, root2);
}
}
return res;
}
private boolean doseSubtree(TreeNode root1,TreeNode root2){if (root2 == null){return true;}
if (root1 == null){return false;}
if (root1.val != root2.val){return false;}
return doseSubtree(root1.left, root2.left) && doseSubtree(root1.right, root2.right);
}
}
5. Python 实现
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
result = False
if pRoot1 and pRoot2: #如果两颗树结点都不为空
if pRoot1.val == pRoot2.val:# 如果结点的值雷同的话
result = self.DoseSubtree(pRoot1, pRoot2)
if not result: # 不雷同,则判断 tree1 左子树结构
result = self.HasSubtree(pRoot1.left, pRoot2)
if not result:
result = self.HasSubtree(pRoot1.right, pRoot2)
return result
def DoseSubtree(self, pRoot1, pRoot2):
if not pRoot2: #如果 tree2 树为空的话,阐明就是子树
return True
if not pRoot1:
return False
if pRoot1.val != pRoot2.val:
return False
# 持续判断 1,2 左子树和 1,2 右子树
return self.DoseSubtree(pRoot1.left, pRoot2.left) and self.DoseSubtree(pRoot1.right, pRoot2.right)
如果您感觉本文有用,请点个“在看”