Leecode 110.判断平衡二叉树

Leecode 110.判断平衡二叉树

平衡二叉树的定义为：给定一个二叉树，每个节点的左右两个子树的高度差绝对值不超过 1 ，同时左右子树也满足上述条件。
如：

给定二叉树 [3, 9, 20, null, null, 15, 7]

    3
   / 
  9  20
    /  
   15   7
根节点的左右子树高度差为1，值为20的子树的左右子树高度差为0，因此返回 true。

而：

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / 
     2   2
    / 
   3   3
  / 
 4   4
根节点的左右子树高度差为2，因此返回 false。

这里要解释一下二叉树高度和深度的定义：
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点(没有左右子树的节点)的最长简单路径边的条数。

求深度可以从上到下的方式计算，因此使用前序遍历(中左右)，求高度则需要使用从下到上的方式，因此使用后序遍历(左右中)。
了解遍历方式之后，我们采用递归来解决此问题:
二叉树树节点定义：

struct TreeNode{
		TreeNOde* left;
		TreeNode* right;
		int val;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
}

一、自上而下(前序遍历)
递归三部曲：
1.确定输入参数：本题需要计算树节点高度，输入树节点指针即可，不需要其他参数， 返回节点高度。即 int getHeight(TreeNode* node);
2.确定终止条件：当遍历到空节点时，高度为0，终止递归。即：if(node == NULL) return 0;
3.单步逻辑：

int geHeight(TreeNode* node){
	if(node == NULL) return 0;
	int leftH = getHeight(node->left);
	int rightH = getHeight(node->right);
	return max(leftH, rightH)+1;
}

整体c++代码：

class Solution{
public:
	int geHeight(TreeNode* node){
		if(node == NULL) return 0;
		int leftH = getHeight(node->left);
		int rightH = getHeight(node->right);
		return max(leftH, rightH)+1; //获取最大高度
	}
	int isBalanced(TreeNode* root){
		if(node == NULL) return true;
		int leftH = getHeight(root->left); //左子树最大高度
		int right = getHeight(root->right); //右子树最大高度
		//左右子树高度差小于2并且左右子树都是平衡二叉树，整体才是平衡二叉树
		return abs(leftH-rightH)<2 && isBalanced(root->left) && isBalanced(root->right);
	}
}

二、自下而上(后序遍历)
上述方法有一个弊端，即：
对于节点 p，如果它的高度是 d，则 getHeight§ 最多会被调用 d 次（即遍历到它的每一个祖先节点）。
自下而上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 −1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
递归三部曲：
1.确定输入参数：本题需要计算树节点高度，输入树节点指针即可，不需要其他参数， 返回节点高度。即 int getHeight(TreeNode* node);
2.确定终止条件：当遍历到空节点时，高度为0，终止递归。即：if(node == NULL) return 0;
3.单步逻辑：

class Solution{
public:
	int geHeight(TreeNode* node){
		if(node == NULL) return 0;
		int leftH = getHeight(node->left);
		if(leftH == -1) return -1; //当左子树不是平衡二叉树时，提前返回
		int rightH = getHeight(node->right);
		if(rightH == -1) return -1;//当右子树不是平衡二叉树时，也提前返回
		return abs(leftH-rightH)>1?-1:max(leftH, rightH)+1; //当高度差大于1，返回-1，否则返回最大高度
	}
	int isBalanced(TreeNode* root){
		return getHeight(root)==-1?false:true;//当返回-1时说明不是平衡二叉树，否则是平衡二叉树
	}
}

参考：
1.https://leetcode-cn.com/problems/balanced-binary-tree/solution/ping-heng-er-cha-shu-by-leetcode-solution/
2.https://zhuanlan.zhihu.com/p/263037657