剑指 Offer 55 - I. 二叉树的深度

题目描述

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：给定二叉树[3,9,20,null,null,15,7]，返回它的最大深度 3 。

🔗题目链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

方法一：前序遍历 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max;
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        getMaxDepth(root, 0);
        return max;
    }
    public void getMaxDepth(TreeNode root, int count){
        if(root == null){
            return;
        }
        count++; //记录节点数
        if(root.left == null && root.right == null){
            //遍历到叶子节点就更新最大深度
            max = Math.max(max, count);
            return;
        }
        getMaxDepth(root.left, count);
        getMaxDepth(root.right, count);
    }
}

方法二：后序遍历 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) { //自底向上，类似于后序遍历
        if(root == null){
            return 0;
        }
        int leftDepth = maxDepth(root.left); //当前节点左子树的深度
        int rightDepth = maxDepth(root.right); //右子树的深度
        return Math.max(leftDepth, rightDepth) + 1; //选择左右深度中最大的进行返回，+1是为了加上当前节点
    }
}

剑指 Offer 55 - II. 平衡二叉树

题目描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

思路

从上到下进行对各节点的左右子树进行判断，
  • 构造一个获取当前节点的最大深度的函数
  • 通过比较某子树的左右子树的深度差  是否成立，来判断某子树是否是平衡二叉树。
  • 从根节点开始，从上到下，先判断根节点的左右子树是否平衡，平衡就接着递归判断左节点和右节点的左右子树是否平衡，以此类推，若所有子树都平衡，则此树平衡。

代码实现 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        //判断当前子树是否平衡
        if(Math.abs(getMaxDepth(root.left) - getMaxDepth(root.right)) <= 1){
            //判断当前子树的左子树和右子树是否平衡
            return isBalanced(root.left) && isBalanced(root.right);
        }
        return false;
    }
    public int getMaxDepth(TreeNode root){ //获得任意节点的左右子树的最大深度
        if(root == null){
            return 0;
        }
        return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
    }
}