【数据结构与算法】二叉树——平衡二叉树

平衡二叉树

LeetCode:平衡二叉

题目描述:

给定一个二叉树,判断它是否是高度平衡的二叉树。

示例:

给定二叉树 [3,9,20,null,null,15,7]
    3
   /   9  20
    /     15   7
返回true

思想:

使用实例域变量记录是否与有不满足平衡的节点出现,使用一次递归即可。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private boolean flag = true;
    //返回高度,并且在递归过程中记录flag
    private int treeDepth(TreeNode root){
        if(root ==null)
            return 0;
        int leftLen = treeDepth(root.left);
        int rightLen = treeDepth(root.right);
        if(Math.abs(leftLen-rightLen)>1)
            flag = false;
        return Math.max(leftLen,rightLen)+1;
    }
    public boolean isBalanced(TreeNode root) {
        int i = treeDepth(root);
        return flag;
    }
}

相关推荐