每日算法之判断是不是平衡二叉树

JZ79 判断是不是平衡二叉树

描述

1. 输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
2. 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
3. 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

复制代码

思路

1. 左右两个子树的高度差的绝对值不超过1
2. 左右两个子树都是一棵平衡二叉树

复制代码

代码

1. package esay.JZ79判断是不是平衡二叉树;
3. class TreeNode {
4.     int val = 0;
5.     TreeNode left = null;
6.     TreeNode right = null;
7.     public TreeNode(int val) {
8.         this.val = val;
9.     }
10. }
12. public class Solution {
13.     //自顶向下
14.     /*public boolean IsBalanced_Solution(TreeNode root) {
15.         //空树也是平衡二叉树
16.         if (root == null) return true;
17.         //左子树深度
18.         int left = deep(root.left);
19.         //右子树深度
20.         int right = deep(root.right);
21.         if (left - right > 1 || right - left > 1) return false;
23.         return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
24.     }
26.     public int deep (TreeNode node) {
27.         if (node == null) return 0;
28.         //左遍历
29.         int left = deep(node.left);
30.         //右遍历
31.         int right = deep(node.right);
32.         return left > right ? left + 1 :right + 1;
33.     }*/
35.     //自底向上
36.     public boolean IsBalanced_Solution(TreeNode root) {
37.         if (root == null) return true;
38.         return getdepth(root) != -1;
39.     }
41.     public int getdepth (TreeNode node) {
42.         if (node == null) return 0;
43.         //左遍历
44.         int left = getdepth(node.left);
45.         if (left < 0) return -1;
46.         //右遍历
47.         int right = getdepth(node.right);
48.         if (right < 0) return -1;
49.         return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
50.     }
52. }

复制代码