二叉树基础oj题目

发布时间:2024年01月21日

二叉树基础oj题目及思路总结

前文中,介绍了二叉树的基本概念及基础操作,进一步对于二叉树的递归遍历及子问题的处理思想有了一定的了解。本文将带来几道二叉树经典的oj题目。

目录

二叉树基础oj题目

  • 对称二叉树
  • 平衡二叉树
  • 二叉树的层序遍历

二叉树基础oj题目

1、对称二叉树

leetcode题目链接
题目描述:给你一个二叉树的根节点 root , 检查它是否轴对称。如下图就是一颗对称二叉树:
在这里插入图片描述
我们可以模拟判断二叉树是不是对称二叉树:
1、对于结点1,左孩子结点为2,右孩子结点为2,目前是对称二叉树。
2、对于1的左孩子结点2,左孩子结点为3,右孩子结点为4, 对于1的右孩子结点2,右孩子结点3,左孩子结点为4,左与右对应,右与左对应,仍是对称二叉树。
可以发现,只要将右子树翻转(左到右,右到左)判断是否与左树相同即可。在总体框架上,仍然使用递归(子问题思路)的方式实现。

 public boolean isSymmetric(TreeNode root) {
        if(root==null) {
            return false;
        }
        return isSameTree(root.left,invertTree(root.right));
    }
    public TreeNode invertTree(TreeNode root) {//翻转二叉树
        if(root==null) return null;
        TreeNode tep = root.left;//引入tmp结点交换左右结点
        root.left = root.right;
        root.right = tep;
        invertTree(root.left);//递归实现子树的翻转
        invertTree(root.right);
        return root;
    }
     public boolean isSameTree(TreeNode p, TreeNode q) {//判断左右树是否相同
        if(p==null&&q!=null||q==null&&p!=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、平衡二叉树

leetcode题目链接
给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。下图就是一颗平衡二叉树。
在这里插入图片描述
这道题目有两个思路:

  • 1、自顶向下的递归
  • 2、自底向上的递归

对于自顶向下的递归,需要对于当前遍历到的节点,首先计算左右子树的高度,如果左右子树的高度差不超过1,再分别递归地遍历左右子节点,并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。这种递归需要计算每一个结点的高度,时间复杂度较高,为O(N^2)。

而对于自底向上的递归,可以递归地判断其左右子树是否平衡,再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的,则返回其高度(高度一定是非负整数),否则返回 ?1。**如果存在一棵子树不平衡,则整个二叉树一定不平衡。**这种递归方式较为高效,时间复杂度为O(N)。

它们之间的根本区别就是自底向上的递归相较于自顶向下的递归,能够记录下底部的结点构成的子树是不是平衡的,一旦不平衡,就可以直接返回-1,得到这棵树不平衡的结论,可以省去在递归过程中许多重复的计算。下面给出自底向上的递归的代码:

public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;//不平衡height()返回的是-1
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 //左右子树已经不都平衡,直接返回-1
        || Math.abs(leftHeight - rightHeight) > 1) {//从高度上判断树不平衡,返回-1
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;//该结点的子树仍平衡,返回最大深度
        }
    }

3、二叉树的层序遍历

leetcode题目链接
给你二叉树的根节点 root ,返回其节点值的 层序遍历。(即逐层地,从左到右访问所有节点)。
如下图所示。
在这里插入图片描述
要解决这个问题,似乎我们不能直接通过递归遍历的方式解决。思考一下,第二层的结点都是第一层的根的孩子结点,第三层的根都是第二层的根的孩子结点…而我们打印的顺序也是从上往下打印,有一种先进先出的感觉,这是我们可以考虑使用队列这种数据结构解决问题。
思路:
**对于第一个结点:1、为空,直接return返回。2、不为空,进入队列。
1、循环条件:队列不为空。2、获取队列长度size。3、判断刚入队结点的左孩子结点与右孩子结点,将不为空的结点入队列。4、将size个结点出队列,并输出这些结点的值。当队列为空时,输出结束。**下面是具体代码的呈现:

public List<List<Integer>> levelOrder(TreeNode root) {//返回的实际上是一个二维数组
        List<List<Integer>> list = new ArrayList<>();
        if(root==null) {
            return list;
        }
        Queue<TreeNode> q = new LinkedList<>();//队列中放的是结点,泛型规定为TreeNode
        q.offer(root);
        while(!q.isEmpty()) {//队列不为空
            List<Integer> l = new ArrayList<>();
            int size = q.size();//获取队列长度
            while(size!=0) {
                TreeNode cur = q.poll();
                l.add(cur.val);
                if(cur.left!=null) {//判断左孩子是否为空
                    q.offer(cur.left);
                }
                if(cur.right!=null) {//判断右孩子是否为空
                    q.offer(cur.right);
                }
                size--;
            }
            list.add(l);//将一维顺序表加到list中
        }
        return list;
    }
文章来源:https://blog.csdn.net/ling_zu_qi/article/details/135721221
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。