平衡二叉树
【题外话】
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。（从上往下看）
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。（从下往上看）
小疑惑：为什么104.二叉树的最大深度中求的是二叉树的最大深度，也用的是后序遍历。（本质上求解的就是根节点的高度，而根节点的高度就是这棵树的最大深度，所以才可以使用后序遍历）
【本题思路】
递归
递归三部曲分析：
1、明确递归函数的参数和返回值
参数：当前传入节点。返回值：以当前传入节点为根节点的树的高度。
如何标记左右子树是否差值大于1呢？
如果当前传入节点为根节点的二叉树已经不是二叉平衡树的话，直接返回-1
代码如下：
// -1表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度 int getHeight(TreeNode *node)
2、明确终止条件
递归的过程中仍然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0
代码如下：
int (node == null) { return 0; }
3、确定单层递归的逻辑
如何判断当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。
int leftHeight = getHeight(node.left); // 左 if (leftHeight == -1) return -1; int rightHeight = getHeight(node.right); //右 if (rightHeight == -1) return -1; int result; if (Math.abs(leftHeight - rightHeight) > 1) { //中 return -1; } else { result = 1 + max(leftHeight, rightHeight); //以当前节点为根节点的树的最大高度 } return result;
整体递归代码如下：
class Solution { public boolean isBalanced(TreeNode root) { return getHeight(root) == -1 ? false : true; } /* 我的想法 public int getHeight(TreeNode node) { if (left == null && right == null) { return true; } int leftDepth = 0; int rightDepth = 0; while (left.left != null) { leftDepth++; } while (right.right != null) { rightDepth++; } if (Math.abs(leftDepth - rightDepth) > 1) { return false; } else { return true; } boolean judgeLeft = judge_Balance(left.left, left.right); boolean judgeRight = judge_Balance(right.left, right.right); return judgeLeft && judgeRight; }*/ public int getHeight(TreeNode root) { if (root == null) { return 0; } int leftHeight = getHeight(root.left); //左 if (leftHeight == -1) return -1; int rightHeight = getHeight(root.right); //右 if (rightHeight == -1) return -1; int result; if (Math.abs(leftHeight - rightHeight) > 1) { return -1; } else { result = 1 + Math.max(leftHeight, rightHeight); } return result; } }
迭代
在104.二叉树的最大深度中我们可以使用层序遍历来求深度，但是就不能直接用层序遍历来求高度了，这就体现出了求高度和求深度的不同。
本题的迭代方式可以先定义一个函数，专门用来求高度。
这个函数用过栈模拟的后序遍历找每一个节点的高度（其实是通过求传入节点为根节点的最大深度来求的高度）
代码如下：
class Solution { /** * 迭代法，效率较低，计算高度时会重复遍历 * 时间复杂度：O(n^2) */ public boolean isBalanced(TreeNode root) { if (root == null) { return true; } Stack<TreeNode> stack = new Stack<>(); TreeNode pre = null; while (root!= null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } TreeNode inNode = stack.peek(); // 右结点为null或已经遍历过 if (inNode.right == null || inNode.right == pre) { // 比较左右子树的高度差，输出 if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) { return false; } stack.pop(); pre = inNode; root = null;// 当前结点下，没有要遍历的结点了 } else { root = inNode.right;// 右结点还没遍历，遍历右结点 } } return true; } /** * 层序遍历，求结点的高度 */ public int getHeight(TreeNode root) { if (root == null) { return 0; } Deque<TreeNode> deque = new LinkedList<>(); deque.offer(root); int depth = 0; while (!deque.isEmpty()) { int size = deque.size(); depth++; for (int i = 0; i < size; i++) { TreeNode poll = deque.poll(); if (poll.left != null) { deque.offer(poll.left); } if (poll.right != null) { deque.offer(poll.right); } } } return depth; } } class Solution { /** * 优化迭代法，针对暴力迭代法的getHeight方法做优化，利用TreeNode.val来保存当前结点的高度，这样就不会有重复遍历 * 获取高度算法时间复杂度可以降到O(1)，总的时间复杂度降为O(n)。 * 时间复杂度：O(n) */ public boolean isBalanced(TreeNode root) { if (root == null) { return true; } Stack<TreeNode> stack = new Stack<>(); TreeNode pre = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } TreeNode inNode = stack.peek(); // 右结点为null或已经遍历过 if (inNode.right == null || inNode.right == pre) { // 输出 if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) { return false; } stack.pop(); pre = inNode; root = null;// 当前结点下，没有要遍历的结点了 } else { root = inNode.right;// 右结点还没遍历，遍历右结点 } } return true; } /** * 求结点的高度 */ public int getHeight(TreeNode root) { if (root == null) { return 0; } int leftHeight = root.left != null ? root.left.val : 0; int rightHeight = root.right != null ? root.right.val : 0; int height = Math.max(leftHeight, rightHeight) + 1; root.val = height;// 用TreeNode.val来保存当前结点的高度 return height; } } JAVA 折叠 复制 全屏
总结：
通过本题可以了解求二叉树深度和二叉树高度的差异，求深度适合用前序遍历，而求高度适合用后序遍历。
本题迭代法其实有点复杂，大家可以有一个思路，也不一定说非要写出来。
但是递归方式是一定要掌握的！
