关于java:LeetCode110平衡二叉树

27次阅读

共计 1467 个字符,预计需要花费 4 分钟才能阅读完成。

均衡二叉树

题目形容:给定一个二叉树,判断它是否是高度均衡的二叉树。

本题中,一棵高度均衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例阐明请见 LeetCode 官网。

起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。

解法一:递归
  • 首先,增加一个办法 height,该办法通过层序遍历的形式失去二叉树的高度。
  • 而后,通过递归法判断二叉树是否是均衡二叉树,递归过程如下:

    • 如果以后根节点为空,则间接返回 true;
    • 否则,计算以后根节点的左右子树的高度,如果以后根节点的左右子树的高度之差不超过 1,则递归判断以后根节点的左右子树是否是均衡二叉树;否则,返回 false。
import com.kaesar.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class LeetCode_110 {
    /**
     * 递归
     *
     * @param root
     * @return
     */
    public static boolean isBalanced(TreeNode root) {
        // 如果以后根节点为 null,必定是均衡的,间接返回 true
        if (root == null) {return true;}
        // 如果以后根节点的左右子树的高度之差不超过 1,则递归判断以后根节点的左右子树是否是均衡二叉树
        if (height(root.left) - height(root.right) >= -1 && height(root.left) - height(root.right) <= 1) {return isBalanced(root.left) && isBalanced(root.right);
        } else {return false;}
    }

    /**
     * 层序遍历:通过计算二叉树的层数来失去二叉树的高度
     *
     * @param root 以后根节点
     * @return 返回二叉树的高度
     */
    public static int height(TreeNode root) {
        int result = 0;
        if (root == null) {return result;}
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        result = 0;
        while (!nodes.isEmpty()) {
            result++;
            int count = nodes.size();
            while (count > 0) {TreeNode cur = nodes.poll();
                if (cur.left != null) {nodes.add(cur.left);
                }
                if (cur.right != null) {nodes.add(cur.right);
                }
                count--;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // 测试用例,冀望返回后果:true
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(isBalanced(root));
    }
}

【每日寄语】 把所有的不快给昨天,把所有的心愿给今天,把所有的致力给明天。

正文完
 0