LeetCode： 剑指 Offer 55 - II. 平衡二叉树
类似 计算树的深度
层序遍历 √
注意这种情况，所以同时需要递归子节点进行左右子树高度的判断
后序遍历法
class Solution { public boolean isBalanced(TreeNode root) { if(root == null) return true; return lankeren(root) != -1; } public int lankeren(TreeNode node){ if(node == null) return 0; int left = lankeren(node.left); if(left == -1) return -1; int right = lankeren(node.right); if(right == -1) return -1; return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1; } }层序遍历法
public boolean isBalanced(TreeNode root) { if(root == null) return true; boolean b = Math.abs(dfs(root.left) - dfs(root.right)) <= 1; boolean f = isBalanced(root.left) && isBalanced(root.right); return b && f; } public int dfs(TreeNode node){ int ans = 1; Queue<TreeNode> queue = new LinkedList<>(); if(node == null) return ans; queue.offer(node); while (!queue.isEmpty()){ int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode temp = ((LinkedList<TreeNode>) queue).pop(); if(temp.left != null) queue.offer(temp.left); if(temp.right != null) queue.offer(temp.right); } // 深度 + 1 ans++; } return ans; }