题目一：二叉树的深度

题目：输入一棵二叉树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

#include<iostream>
using namespace std;
struct BinaryTreeNode{
	int value;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
};
int TreeDepth(BinaryTreeNode* pRoot){
	if(pRoot==NULL) return 0;
	
	int left=TreeDepth(pRoot->left);
	int right=TreeDepth(pRoot->right);
	return (left>right)?(left+1):(right+1);
}
int main() {
	return 0;
}

题目二：平衡二叉树

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

🐛需要重复遍历节点多次的解法，简单但不足以打动面试官

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct BinaryTreeNode{
	int value;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
};
int TreeDepth(BinaryTreeNode* pRoot){
	if(pRoot==NULL) return 0;
	
	int left=TreeDepth(pRoot->left);
	int right=TreeDepth(pRoot->right);
	return (left>right)?(left+1):(right+1);
}
bool isBalance(BinaryTreeNode* pRoot){
	if(pRoot==NULL) return true;
	
	int left=TreeDepth(pRoot->left);
	int right=TreeDepth(pRoot->right);
	if(abs(left-right)>1) return false;
	
	return isBalance(pRoot->left)&&isBalance(pRoot->right);
}
int main() {
	return 0;
}

🐛每个节点只遍历一次的解法，正是面试官喜欢的（利用后序遍历的思想）

#include<iostream>
using namespace std;
struct BinaryTreeNode{
	int value;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
};
bool isBalance(BinaryTreeNode* pRoot, int* pDepth){
	if(pRoot==NULL) {
		*pDepth=0;
		return true;
	}
	int left, right;
	if(isBalance(pRoot->left, &left) && isBalance(pRoot->right, &right)){
		int diff=left-right;
		if(diff<=1 && diff>=-1){
			*pDepth=1+(left>right?left:right);
			return true;
		}
	} 
	
	return false;
}
bool isBalance(BinaryTreeNode* pRoot){
	int depth=0;
	return isBalance(pRoot, &depth);
}
int main() {
	return 0;
}