【数据结构与算法】二叉树——平衡二叉树
平衡二叉树
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; } }