判断平衡二叉树

港控/mmm° 2022-04-15 01:07 233阅读 0赞

[平衡二叉树][Link 1]（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。并且左右两个子树都是一棵平衡二叉树

（不是我们平时意义上的必须为搜索树）

判断一棵树是否为平衡二叉树：

可以暴力判断：每一颗树是否为平衡二叉树。

分析：

如果左右子树都已知是平衡二叉树，而左子树和右子树高度差绝对值不超过1，本树就是平衡的。

为此我们需要的信息：左右子树是否为平衡二叉树。左右子树的高度。

我们需要给父返回的信息就是：本棵树是否是平衡的、本棵树的高度。

定义结点和返回值：

public static class Node {
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}

public static class ReturnType {
    		public int level;   //深度
    		public boolean isB;//本树是否平衡
    		
    		public ReturnType(int l, boolean is) {
    			level = l;
    			isB = is;
    		}
    	}

我们把代码写出来：

// process(head, 1)
    	
    	public static ReturnType process(Node head, int level) {
    		if (head == null) {
    			return new ReturnType(level, true);
    		}
    		//取信息
    		ReturnType leftSubTreeInfo = process(head.left, level + 1);
    		if(!leftSubTreeInfo.isB) {
    			return new ReturnType(level, false);     //左子树不是->返回
    		}
    		ReturnType rightSubTreeInfo = process(head.right, level + 1);
    		if(!rightSubTreeInfo.isB) {
    			return new ReturnType(level, false);     //右子树不是->返回
    		}
    		if (Math.abs(rightSubTreeInfo.level - leftSubTreeInfo.level) > 1) {
    			return new ReturnType(level, false);     //左右高度差大于1->返回
    		}
    		
    		return new ReturnType(Math.max(leftSubTreeInfo.level, rightSubTreeInfo.level), true);
    		//返回高度和true（当前树是平衡的）
    	}

我们不需要每次都返回高度，用一个全局变量记录即可。

对于其它二叉树问题，可能不止一个变量信息，所以，全局记录最好都养成定义数组的习惯。

下面贴出完整代码：

import java.util.LinkedList;
    import java.util.Queue;
    
    public class Demo {
    	public static class Node {
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}
    	public static boolean isBalance(Node head) {
    		boolean[] res = new boolean[1];
    		res[0] = true;
    		getHeight(head, 1, res);
    		return res[0];
    	}
    	
    	public static class ReturnType {
    		public int level;   //深度
    		public boolean isB;//本树是否平衡
    		
    		public ReturnType(int l, boolean is) {
    			level = l;
    			isB = is;
    		}
    	}
    	
    	// process(head, 1)
    	
    	public static ReturnType process(Node head, int level) {
    		if (head == null) {
    			return new ReturnType(level, true);
    		}
    		//取信息
    		ReturnType leftSubTreeInfo = process(head.left, level + 1);
    		if(!leftSubTreeInfo.isB) {
    			return new ReturnType(level, false);     //左子树不是->返回
    		}
    		ReturnType rightSubTreeInfo = process(head.right, level + 1);
    		if(!rightSubTreeInfo.isB) {
    			return new ReturnType(level, false);     //右子树不是->返回
    		}
    		if (Math.abs(rightSubTreeInfo.level - leftSubTreeInfo.level) > 1) {
    			return new ReturnType(level, false);     //左右高度差大于1->返回
    		}
    		
    		return new ReturnType(Math.max(leftSubTreeInfo.level, rightSubTreeInfo.level), true);
    		//返回高度和true（当前树是平衡的
    	}
    
    	public static int getHeight(Node head, int level, boolean[] res) {
    		if (head == null) {
    			return level;//返回高度
    		}
    		//取信息
    		//相同逻辑
    		int lH = getHeight(head.left, level + 1, res);
    		if (!res[0]) {
    			return level;
    		}
    		int rH = getHeight(head.right, level + 1, res);
    		if (!res[0]) {
    			return level;
    		}
    		if (Math.abs(lH - rH) > 1) {
    			res[0] = false;
    		}
    		return Math.max(lH, rH);//返回高度
    	}
    
    	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));
    
    	}
    
    }

[Link 1]: https://baike.baidu.com/item/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91