平衡二叉树

题目描述

力扣链接🔗

平衡二叉树 - 图1

题目分析

高度和深度的概念在二叉树概述中。此题注意：而根节点的高度就是这棵树的最大深度。

代码

递归法

  1. 明确递归函数的参数和返回值
    参数：当前传入节点。
    返回值：以当前传入节点为根节点的树的高度。
    那么如何标记左右子树是否差值大于1呢？如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
  2. 明确终止条件
    递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0。
  3. 单层循环
    求当前左子树和右子树的高度差，如果相差大于一，那么就已经不是平衡二叉树了，此时需要将结果返回-1，标志此时已经不是平衡二叉树。如果上一次递归返回的结果为-1，那么直接返回-1，表示不是平衡二叉树。 
  1. /**
  2.  * 后序递归法
  3.  * @param root
  4.  * @return
  5.  */
  6. public boolean isBalanced(TreeNode root) {
  7.     return getHeight(root) == -1 ? false : true;
  8. }
  10. // -1表示此时高度差已经大于1
  11. public int getHeight(TreeNode root) {
  12.     if (root == null) {
  13.         return 0;
  14.     }
  16.     int leftHeight = getHeight(root.left);  // 左
  17.     if (leftHeight == -1) return -1;
  18.     int rightHeight = getHeight(root.right);// 右
  19.     if (rightHeight == -1) return -1;
  20.     if (Math.abs(leftHeight - rightHeight) > 1) {   // 中
  21.         return -1;  // 左右子树高度相差大于1，返回-1
  22.     } else {
  23.         return 1 + Math.max(leftHeight, rightHeight); // 左右子树高度相差小于1，此节点作为根节点的高度就为最大深度
  24.     }
  25. }

先序也可以

  1. public boolean isBalanced(TreeNode root) {
  2.     if (root == null) {
  3.         return true;
  4.     }
  6.     if (isBalanced(root.left) == false) return false;
  7.     if (isBalanced(root.right) == false) return false;
  9.     int left = traversal(root.left);
  10.     int right = traversal(root.right);
  12.     return Math.abs(left - right) <= 1;
  13. }
  15. public int traversal(TreeNode root) {
  16.     if (root == null) {
  17.         return 0;
  18.     }
  19.     int left = traversal(root.left);
  20.     int right = traversal(root.right);
  21.     return 1 + Math.max(left, right);
  22. }

迭代法

定义一个求深度的方法，每次遍历一个节点就求其深度，然后再按照上述递归法思路判断左右孩子是否相差1。

  1. /**
  2.  * 迭代法（时间复杂度O(n ^ n)）
  3.  *
  4.  * @param root
  5.  * @return
  6.  */
  7. public boolean isBalanced(TreeNode root) {
  8.     if (root == null) return true;
  9.     // 然后再用栈来模拟前序遍历，遍历每一个节点的时候，再去判断左右孩子的高度是否符合
  10.     Stack<TreeNode> stack = new Stack<>();
  11.     stack.push(root);
  12.     int leftHeight = 0, rightHeight = 0;
  14.     while (!stack.isEmpty()) {
  15.         TreeNode node = stack.pop();
  16.         leftHeight = getHeight(node.left);
  17.         rightHeight = getHeight(node.right);
  18.         if (Math.abs(leftHeight - rightHeight) > 1) {   // 中
  19.             return false;
  20.         } else {
  21.             if (node.right != null) isBalanced(node.right);  // 右（空节点不入栈）
  22.             if (node.left != null) isBalanced(node.left);  // 左（空节点不入栈）
  23.         }
  24.     }
  25.     return true;
  26. }
  28. /**
  29.  * 层序求深度
  30.  *
  31.  * @param root
  32.  * @return
  33.  */
  34. public int getHeight(TreeNode root) {
  35.     if (root == null) {
  36.         return 0;
  37.     }
  38.     Queue<TreeNode> queue = new LinkedList<>();
  39.     queue.offer(root);
  40.     int height = 0;
  41.     while (!queue.isEmpty()) {
  42.         int len = queue.size();
  43.         height++;
  45.         while (len > 0) {
  46.             TreeNode node = queue.poll();
  47.             if (node.left != null) queue.offer(node.left);
  48.             if (node.right != null) queue.offer(node.right);
  49.             len--;
  50.         }
  52.     }
  53.     return height;
  54. }

求深度适合用前序遍历，而求高度适合用后序遍历。