当前位置：首页 > article >正文

【数据结构和算法实践-树-LeetCode110-平衡二叉树】

article 2024/11/12 20:43:42

数据结构和算法实践-树-LeetCode110-平衡二叉树

- 题目
- My Thought
- 代码示例
- - JAVA-8

题目

给定一个二叉树，判断它是否是
平衡二叉树

输入：root = [3,9,20,null,null,15,7]
输出：true

My Thought

判断平衡二叉树的条件是树的左右高度相差为1
一、利用递归去遍历
1、边界为节点为null，树高为0；
2、树高的递增规则为，根的左节点和右节点比较值+1
二、为了方便信息传递，需要设置一个实体存储高度和是否平衡

代码示例

JAVA-8

    public boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }

    private NodeInfo process(TreeNode root) {
        if (root == null) {
            return new NodeInfo(0, true);
        }
        NodeInfo leftNode = process(root.left);
        NodeInfo rightNode = process(root.right);
        int height = Math.max(leftNode.height, rightNode.height) + 1;
        boolean isBalanced = leftNode.isBalanced && rightNode.isBalanced && Math.abs(leftNode.height - rightNode.height) < 2;
        return new NodeInfo(height, isBalanced);
    }