LeetCode110-Balanced Binary Tree

落日映苍穹つ 2022-08-04 12:48 27阅读 0赞

**LeetCode 110 : Balanced Binary Tree**

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

问题来源： [https://leetcode.com/problems/balanced-binary-tree/][https_leetcode.com_problems_balanced-binary-tree]

问题的大概意思是给一个二叉树，判断该树是否为平衡二叉树（平衡二叉树的判断条件：左右子树的高度相差最大不超过1）。

解题思路：通过递归找出每一个二叉树的左右子树的高度，然后比较左右子树高度差是否不超过1。注意若该树为空也满足条件。

源代码：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public boolean isBalanced(TreeNode root) {
            if(null==root){
                return true;
            }
            else{
                return isBalancedTree(root);
            }
        }
        private boolean isBalancedTree(TreeNode node){
            if(null==node){
                return true;
            }
            else{
                int leftChildHeight = getHeight(node.left);
                int rightChildHeight = getHeight(node.right);
                return (Math.abs(leftChildHeight-rightChildHeight)<=1) && isBalancedTree(node.left) && isBalancedTree(node.right);
            }
        }
        private int getHeight(TreeNode node){
            if(null==node){
                return 0;
            }
            else{
                int leftChildHeight = getHeight(node.left);
                int rightChildHeight = getHeight(node.right);
                return (leftChildHeight >= rightChildHeight) ? leftChildHeight+1 : rightChildHeight+1;
            }
        }
    }

[https_leetcode.com_problems_balanced-binary-tree]: https://leetcode.com/problems/balanced-binary-tree/