Article Outline
TOC
Collection Outline
判断一棵二叉树是否是平衡二叉树
【平衡二叉树概念】当二叉树的任意一棵子树的左子树的高度和右子树的高度相差不超过 1 时,该二叉树为平衡二叉树。
【解答方案】根据定义可知,要确认一个二叉树是否是平衡二叉树势必要遍历所有结点。
即将问题分解为:只要保证以每个结点为根节点的树是否平衡;而遍历到每个结点时,要想知道以该结点为根结点的子树是否是平衡二叉树,首先判断该结点的左子树是否平衡,然后判断该结点的右子树是否平衡,如果两个子树都平衡,分别计算左子树和右子树的高度。因此我们要收集两个信息:
该结点的左子树、右子树是否是平衡二叉树
左右子树的高度分别是多少,相差是否超过 1
那么我们来到某个结点时(子过程),我们需要向上层(父过程)返回的信息就是该结点为根结点的树是否是平衡二叉树以及以该结点为根的树高度,这样的话,父过程就能继续向上层返回应该收集的信息。
【方案改进】 因为使用递归进行二叉树的遍历的时候,每个递归函数会到一个节点 3 次:首先会到一次,然后访问左子树之后会回来一次,最后访问右子树之后会回来一次; 对于二叉树使用递归的时候,首先想办法收集一下左子树上的信息,然后想办法收集一下右子树上的信息,最后将这些信息进行整合皆可以得到该结点所在的整棵树符不符合标准;本题中的标准就是判断该数是否平衡;
/**
* 判断是否为平衡树
*
* @author GJXAIOU
*/
public class IsBalancedTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
public static boolean isBalance(Node head) {
// 这里需要使用数组,因为作为参数传入 getHeight 函数,同时在该函数中修改了值,需要同步修改这里的值返回值才会变化。
boolean[] res = new boolean[1];
res[0] = true;
getHeight(head, 1, res);
return res[0];
}
public static int getHeight(Node head, int level, boolean[] res) {
if (head == null) {
return level;
}
int leftHeight = getHeight(head.left, level + 1, res);
if (!res[0]) {
return level;
}
int rightHeight = getHeight(head.right, level + 1, res);
if (!res[0]) {
return level;
}
// 如果左右高度差大于 1 则返回 false
if (Math.abs(leftHeight - rightHeight) > 1) {
res[0] = false;
}
return Math.max(leftHeight, rightHeight);
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(7);
System.out.println(isBalance(head));
}
}
注:递归过程总结
递归很好用,该题中的递归用法也是一种经典用法,可以高度套路:
- 分析问题的解决需要哪些步骤(这里是遍历每个结点,确认每个结点为根节点的子树是否为平衡二叉树)
- 确定递归:父问题是否和子问题相同
- 子过程要收集哪些信息
- 本次递归如何利用子过程返回的信息得到本过程要返回的信息
- 处理
base case