二叉树基础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;
    }