【数据结构】——二叉树oj题详解
1、100. 相同的树 - 力扣(LeetCode)
我们考虑它相同和不相同的情况,再用递归遍历:
完整代码:
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q != null || p != null && q == null){
return false;
}
if (p == null && q == null){
return true;
}
if(p.val != q.val){
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
2、572. 另一棵树的子树 - 力扣(LeetCode)
这道题,我们可以直接用上一道题的代码,其思路如下:
- 我们首先判断root和subRoot是不是两颗相同的树,是的话就返回true
- 不是的话,就继续判断subRoot是不是root.left的左子树的子树或者root.left是不是和和subRoot为相同的树
- 同理再判断subRoot和root.right;
完整代码:
class Solution {
//时间复杂度为:n * m
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q != null || p != null && q == null) {
return false;
}
if(p == null && q == null) {
return true;
}
if(p.val != q.val) {
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null || subRoot == null){
return false;
}
if (isSameTree(root,subRoot)){
return true;
}
if(isSubtree(root.left,subRoot)){
return true;
}
if(isSubtree(root.right,subRoot)){
return true;
}
return false;
}
}
3、110. 平衡二叉树 - 力扣(LeetCode)
思路:
- 首先这道题判断平衡也就是左右子树的高度差,那就需要求出左右子树的高度,,进行比较
- 然后还需要求出左子树的子树的高度差,和右子树的子树的高度差,来判断左子树和右子树是否平衡。
- 所以需要遍历树的每一个结点
完整代码:
class Solution {
//时间复杂度为:n * n
int getHeight(TreeNode root){
if (root == null){
return 0;
}
int leftTree = getHeight(root.left);
int rightTree = getHeight(root.right);
return leftTree > rightTree ? leftTree+1 : rightTree+1;
}
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return Math.abs(leftHeight-rightHeight) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}
}
上面的这种解法的时间复杂度是O(n^2),会出现大量的的重复计算,当计算根结点的左子树高度时,递归到数字九时返回一个2就已经说明了该树不平衡,所以我们从下向上计算高度时顺便判断一下,这样的话时间复杂度就是O(n):
class Solution {
int getHeight(TreeNode root){
if (root == null){
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1){
return Math.max(leftHeight,rightHeight) + 1;
}else{
//返回-1 就说明已经出现了不平衡
return -1;
}
}
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
return getHeight(root) >= 0;
}
}
4、101. 对称二叉树 - 力扣(LeetCode)
思路就是判断root的左右子树是否对称:左子树的右树和右子树的左树是否相同:
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}
return isSymmetricChild(root.left,root.right);
}
private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
//判断左子树的右树和右子树的左树是否相同.
if (leftTree == null && rightTree != null || leftTree != null && rightTree == null){
return false;
}
//是否都为空
if (leftTree == null && rightTree == null){
return true;
}
//判断val值
if (leftTree.val != rightTree.val){
return false;
}
//进行递归左子树的右树和右子树的左树
return isSymmetricChild(leftTree.left, rightTree.right) &&
isSymmetricChild(leftTree.right, rightTree.left);
}
}
5、102. 二叉树的层序遍历 - 力扣(LeetCode)
思路:
- 首先要创建两个顺序表来分层存储二叉树
- 创建一个队列,先把根结点入对,再把top弹出的同时并赋值给cur并打印
- 并且把top的左右子树入队,直到树为空
完整代码:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if(root == null){
return ret;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> leve = new ArrayList<Integer>();
int queue_size = queue.size();
for(int i = 0; i < queue_size; i++){
TreeNode node = queue.poll();
leve.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
ret.add(leve);
}
return ret;
}
}
6、判断该树是否为完全二叉树
思路:
- 将null也入队,如果队列中只剩下null,说明就为完全二叉树
- 当非完全二叉树入队时,出队的时候会发现队列中还剩下null和结点
完整代码:
boolean isCompleteTree(TreeNode root){
if (root == null){
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode cur = queue.poll();
if (cur != null){
queue.offer(cur.left);
queue.offer(cur.right);
}else {
break;
}
}
while (!queue.isEmpty()){
TreeNode cur = queue.peek();
if (cur != null){
//不是完全二叉树
return false;
}else {
queue.poll();
}
}
return true;
}