LeetCode二叉树简单题汇总

前言

刷了一部分LeetCode的题，感觉自己对二叉树的运用提升了不少，便总结分享一下。博客里用的都是比较好理解的递归算法，效率不一定最高，适合跟我差不多的小白。
本篇博客只给出如下的部分题，二叉搜索树等我积累够了的之后单独出一篇

然后给出下面的题都需要用到的二叉树类

public class TreeNode{
        int val;
        TreeNode right;
        TreeNode left;
        TreeNode(int val){this.val=val;}
    }

101. 对称二叉树

题目

解答

一定要注意这里是镜像对称，不只是简单的左子树==右子树，而是左子树的左子树==右子树的右子树并且左子树的右子树==右子树的左子树。所以再重载两个参数的函数来实现要简单一点，这样可以比较r1.left==r2.right且r1.right==r2.left

 public boolean isSymmetric(TreeNode root) {
          if (root==null) return true;
          else return isSymmertric(root.left, root.right);
    }
     public boolean isSymmertric(TreeNode r1, TreeNode r2){
        if (r1==null && r2== null) return true;
        else if (r1 == null || r2 == null) return false;
        else if(r1.val != r2.val) return false;
        else return isSymmertric(r1.left,r2.right) && isSymmertric(r1.right, r2.left);
    }

110. 平衡二叉树

题目

解答

这种题目用递归都比较好思考，首先可以用递归求左右子树的深度，再比较深度相差是否大于1，大于1就false；否则继续检查左右子树是否为平衡二叉树，这里也有递归，所以是双重递归。

需要递归的检查左右子树，平衡二叉树定义是对于每个节点的深度差，不只指根节点的左右子树深度差；简单的说，平衡二叉树的左右子树也是平衡二叉树

    //常规的求深度操作，不用多说了吧
    private int maxDepth(TreeNode root){
        if (root==null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }
   public boolean isBalanced(TreeNode root) {
         if (root==null) return true;
        int l = maxDepth(root.left);//左子树深度
        int r = maxDepth(root.right);//右子树深度
        if (Math.abs(l - r) > 1) return false;//深度差大于1，非平衡
        return isBalanced(root.left) && isBalanced(root.right);//根节点平衡，检查下面的节点是否也平衡
    }

226. 翻转二叉树

题目

解答

非常朴素地递归思想，想用自己的递归函数翻转左右子树，再交换当前的左右子树。

    public TreeNode invertTree(TreeNode root) {
        if (root==null) return null;
        invertTree(root.left);//先翻转左子树
        invertTree(root.right);//再翻转右子树
        //这时候左右子树翻转好了，交换当前的左右子树，常规的三行交换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }

543. 二叉树的直径

题目

解答

我依旧将问题转化为了二叉树的深度，单个节点的直径为左子树深度+右子树深度；求出每个节点的直径，找到最大就行。

   //求深度
   private int height(TreeNode root){
        if (root==null) return 0;
        return Math.max(height(root.left), height(root.right))+1;
    }
    //求直径
    public int diameterOfBinaryTree(TreeNode root) {
        if (root==null) return 0;
        int max = height(root.left)+height(root.right);//当前节点的直径
        if (root.left!=null) max=Math.max(diameterOfBinaryTree(root.left), max);//和左子树的直径比较取大
        if (root.right!=null) max=Math.max(diameterOfBinaryTree(root.right), max);//和右子树的直径比较取大
        return max;
    }

上面是我最开始的想法，提交了后发现太慢，于是学习了一下网友们的方法：直接求左子树右子树深度和的最大，而不是我那样分别求左子树深度、右子树深度再求和。

	private int max = 0;//利用一个全局变量，记录左右子树深度和的最大值
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return max;
    }
    //本质还是求深度的函数
    private int height(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = height(root.left), rightHeight = height(root.right);
        max = Math.max(leftHeight + rightHeight, max);//多的就是更新深度和的最大值
        return Math.max(leftHeight, rightHeight) + 1;
    }

563. 二叉树的坡度

题目

先定义了单个节点的坡度，再定义了整个树的坡度为节点坡度之和，那么朴素地求解思路就是求出每个节点的坡度，再求总和。

解答

首先解决求和的问题，单独封装一个函数，用递归来解决；

 //递归求和
 private int calSum(TreeNode root){
        if (root==null) return 0;
        return root.val+calSum(root.left)+calSum(root.right);
    }
 //求坡度
 public int findTilt(TreeNode root) {
      if (root==null) return 0;
      int sum = Math.abs(calSum(root.left)-calSum(root.right));//单个节点坡度
      sum += findTilt(root.left);//左子树的坡度
      sum += findTilt(root.right);//右子树的坡度
      return sum;
  }

617. 合并二叉树

题目

解答

自己最开始的笨想法就是，创建新的节点，来合并原来的两棵树

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1==null&&t2==null) return null;
        //合并两棵树根节点的值，这三行可以简化
        TreeNode root = new TreeNode(0);
        if (t1!=null) root.val+=t1.val;
        if (t2!=null) root.val+=t2.val;
        //简化为：TreeNode root = new TreeNode((t1 == null ? 0 : t1.val) + (t2 == null ? 0 : t2.val));
        //递归往下合并子树，这部分也可以简化
        if (t1!=null) {
        //都为null再开头已经考虑，这里的null判断，一共三种情况：
        //1. t1!=nullt2==null  2. t1!=nullt2!=null  3. t1==nullt2!=null
            if (t2==null){
                root.left = mergeTrees(t1.left,null);
                root.right = mergeTrees(t1.right,null);
            }
            else{
                root.left = mergeTrees(t1.left,t2.left);
                root.right = mergeTrees(t1.right,t2.right);
            }
        }
        else{
            root.left = mergeTrees(null, t2.left);
            root.right = mergeTrees(null, t2.right);
        }
        //简化如下：
        //root.left = mergeTrees(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
        //root.right = mergeTrees(t1 == null ? null : t1.right, t2 == null ? null : t2.right);
        return root;
    }

但是这里面需要考虑很多为null的情况，自己也调试了很久；之后从评论中学到了原地修改的算法，极大简化了代码，也更好理解了。

    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        // 先合并根节点
        t1.val += t2.val;
        // 再递归合并左右子树
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }

965. 单值二叉树

题目

解答

这个思路很清晰了，先比较当前节点和左右直接子节点的值是否相当，遇到不相等就false；相等就继续递归判断左右子树是否为单值二叉树。

    public boolean isUnivalTree(TreeNode root) {
        if (root==null) return true;
        if (root.left!=null && root.left.val!=root.val) return false;
        if (root.right!=null && root.right.val!=root.val) return false;
        return isUnivalTree(root.left) && isUnivalTree(root.right);
    }

993. 二叉树的堂兄弟节点

题目

解答

这道题我习惯用层次遍历求解，为了帮助大家理解，先给出我自己的层次遍历模版

• 只遍历，不分层

		Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()){
            //取出当前节点
            TreeNode node = queue.poll();
            System.out.println(node.val);
            //放入当前节点的左右节点
            if (node.left!=null) queue.offer(node.left);
            if (node.right!=null) queue.offer(node.right);
        }

• 即遍历，又分层

 Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        queue.offer(null);//null作为分层的标志
        int height = 0;
        while (!queue.isEmpty()){
            //取出当前节点
            TreeNode node = queue.poll();
            if (node!=null){//因为null作为标志，取出后需要判断是否为null
                System.out.println(node.val);
                //放入当前节点的左右节点
                if (node.left!=null) queue.offer(node.left);
                if (node.right!=null) queue.offer(node.right);
            }else{
                System.out.println("height"+height);//输出当前深度
                height++;//更新深度
                if (!queue.isEmpty()) queue.offer(null);//遍历未结束追加null标记，作为分层依据
            }
        }

• 应用模版进行解答
  将问题转化为判断两个节点深度是否相同，再排除掉共父节点的情况。

    public boolean isCousins(TreeNode root, int x, int y) {
        //用队列实现层次遍历，用null作为分层标志
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        queue.offer(null);
        int height = 0, xHeight=-1, yHeight=0;
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (node!=null) {
                //记录x和y的深度
                if (node.val==x) xHeight=height;
                else if (node.val==y) yHeight=height;
                //不为null放入
                if (node.left!=null) queue.offer(node.left);
                if (node.right!=null) queue.offer(node.right);
                //同父节点提前结束
                if (node.left!=null && node.right!=null){
                    if (node.left.val==x && node.right.val==y) return false;
                    else if (node.left.val==y && node.right.val==x) return false;
                }
            }
            else {
                height++;//更新深度
                if (!queue.isEmpty()) queue.offer(null);//未结束则添加null标记进行分层
            }
        }
        return xHeight==yHeight;//判断深度是否相同