LeetCode【110. 平衡二叉树】

时间:2022-12-17 17:28:21

对于平衡二叉树,就是左右深度相差1

就可以另外弄一个函数,计算深度,然后, 在原函数上进行比较深度是否相差1,再输出true or false。

至于迭代就可以,比较完左右节点,再比较各自的左右节点。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null)
        {
            return true;
        }
        else
        {
            if(depth(root.left) - depth(root.right) > 1 || depth(root.right) - depth(root.left) >1)
            {
                return false;
            }
            else 
                return isBalanced(root.left)&&isBalanced(root.right);
        }
    }
    public int depth(TreeNode root)
    {
        if(root == null)
        {
            return 0;
        }
        else
        {
            int left;
            int right;
            left = depth(root.left);
            right = depth(root.right);
            if(left>right)
            {
                return left+1;
            }
            else
            {
                return right+1;
            }
        }
    }
}