• 一、题目
  • 二、解题思路
  • 三、解题代码

    一、题目

    输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1 ,那么它就是一棵平衡二叉树。

    二、解题思路

    解法一:需要重蟹遍历结点多次的解法
    在遍历树的每个结点的时候,调用函数treeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1 ,按照定义它就是一棵平衡的二叉树。

    解法二:每个结点只遍历一次的解法
    用后序遍历的方式遍历二叉树的每一个结点,在遍历到一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度(某一结点的深度等于它到叶节点的路径的长度),我们就可以一边遍历一边判断每个结点是不是平衡的。

    三、解题代码

    1. public class Test {
    2. private static class BinaryTreeNode {
    3. int val;
    4. BinaryTreeNode left;
    5. BinaryTreeNode right;
    6. public BinaryTreeNode() {
    7. }
    8. public BinaryTreeNode(int val) {
    9. this.val = val;
    10. }
    11. }
    12. public static int treeDepth(BinaryTreeNode root) {
    13. if (root == null) {
    14. return 0;
    15. }
    16. int left = treeDepth(root.left);
    17. int right = treeDepth(root.right);
    18. return left > right ? (left + 1) : (right + 1);
    19. }
    20. /**
    21. * 判断是否是平衡二叉树,第一种解法
    22. *
    23. * @param root
    24. * @return
    25. */
    26. public static boolean isBalanced(BinaryTreeNode root) {
    27. if (root == null) {
    28. return true;
    29. }
    30. int left = treeDepth(root.left);
    31. int right = treeDepth(root.right);
    32. int diff = left - right;
    33. if (diff > 1 || diff < -1) {
    34. return false;
    35. }
    36. return isBalanced(root.left) && isBalanced(root.right);
    37. }
    38. /**
    39. * 判断是否是平衡二叉树,第二种解法
    40. *
    41. * @param root
    42. * @return
    43. */
    44. public static boolean isBalanced2(BinaryTreeNode root) {
    45. int[] depth = new int[1];
    46. return isBalancedHelper(root, depth);
    47. }
    48. public static boolean isBalancedHelper(BinaryTreeNode root, int[] depth) {
    49. if (root == null) {
    50. depth[0] = 0;
    51. return true;
    52. }
    53. int[] left = new int[1];
    54. int[] right = new int[1];
    55. if (isBalancedHelper(root.left, left) && isBalancedHelper(root.right, right)) {
    56. int diff = left[0] - right[0];
    57. if (diff >= -1 && diff <= 1) {
    58. depth[0] = 1 + (left[0] > right[0] ? left[0] : right[0]);
    59. return true;
    60. }
    61. }
    62. return false;
    63. }
    64. }