本篇主要写二叉树的结构，中序、前序、后序、层序遍历算法。

二叉树的结构，本篇以如下这个二叉树进行遍历：

中序遍历：左子节点---->中间节点---->右子节点

前序遍历：中间节点----->左子节点---->右子节点

后序遍历:  左子节点----->右子节点----->中间节点

层序遍历：一层一层的从上往下遍历

以上图二叉树结构为例，开始编写代码：

#include <iostream>
#include <queue>
using namespace std;


template <class T> class BinaryTree;


template <class T>
class TreeNode
{
	template <class T>
	friend class BinaryTree;
public:

	TreeNode(const T & d):data(d)
	{
		leftChild = rightChild = NULL;
	}
//private:
	T data;
	TreeNode *leftChild;
	TreeNode *rightChild;

};

template <class T>
class BinaryTree
{
public:
	void InOrder(); //中序遍历    左->中->右
	void InOrder(TreeNode<T> * current);  
	void PreOrder(); //前序遍历  中->左->右
	void PreOrder(TreeNode<T> *current);
	void PostOrder();//后序遍历  左->右->中
	void PostOrder(TreeNode<T>*current);
	void LevelOrder(); //层序遍历
	void Visit(TreeNode<T>*current);

	int getTreeHight(TreeNode<T>* root);  //计算思路:树的深度=左链的深度和右链深度的最大值 +1

	TreeNode<T> *  getRoot()
	{
		return root;
	}

//private:
	TreeNode<T> *root;

};

template <class T>
void BinaryTree< T>::Visit(TreeNode<T>*current)
{
	if (current)
		cout << current->data << " ";
}
template <class T>
void BinaryTree< T>::InOrder(TreeNode<T>*current)
{
	if (current)
	{
		InOrder(current->leftChild);
		Visit(current);
		InOrder(current->rightChild);
	}
}
template <class T>
void BinaryTree< T>::InOrder()
{
	InOrder(root);
}
template <class T>
void BinaryTree<T>::PreOrder()
{
	PreOrder(root);
}
template <class T>
void BinaryTree<T>::PreOrder(TreeNode<T> *current)
{
	if (current)
	{
		Visit(current);
		PreOrder(current->leftChild);
		PreOrder(current->rightChild);
	}
}

template <class T>
void BinaryTree<T>::PostOrder()
{
	PostOrder(root);
}

template <class T>
void BinaryTree<T>::PostOrder(TreeNode<T> *current)
{
	if (current)
	{
		PostOrder(current->leftChild);
		PostOrder(current->rightChild);
		Visit(current);
	}
}

template <class T>
void BinaryTree<T>::LevelOrder()
{
	//层序遍历，充分利用了queue先进先出的特点
	queue<TreeNode<T>* > q;

	TreeNode<T>* current = root;

	while (current)
	{
		Visit(current);
		if (current->leftChild) q.push(current->leftChild); //先把左子节点放到队列
		if (current->rightChild) q.push(current->rightChild); //再把右子节点放到队列

		if (q.empty()) return;  //到队列空的时候就返回

		current = q.front(); //当前指针指向先放进去的指针
		q.pop();  //将上边这个弹出队列
	}
}

template <class T>
int BinaryTree<T>::getTreeHight(TreeNode<T>* root) 
{
	if (NULL == root)
		return 0;

	int leftHigh = getTreeHight(root->leftChild);
	int rightHigh = getTreeHight(root->rightChild);

	int maxHigh = leftHigh >= rightHigh ? leftHigh + 1 : rightHigh + 1;

	return maxHigh;

}

int main()
{
	TreeNode<char> node1('+'),node2('-'), node3('*'), node4('/'), node5('A'), node6('B'), node7('C'), node8('D'), node9('E');

	BinaryTree<char> tree;
	

	tree.root = &node1;

	node1.leftChild = &node2;
	node1.rightChild = &node9;

	node2.leftChild = &node3;
	node2.rightChild = &node8;

	node3.leftChild = &node4;
	node3.rightChild = &node7;

	node4.leftChild = &node5;
	node4.rightChild = &node6;

	//中序遍历
	cout << "中序遍历:   ";
	tree.InOrder();
	cout << endl;

	//前序遍历
	cout << "前序遍历:   ";
	tree.PreOrder();
	cout << endl;

	//后序遍历
	cout << "后序遍历:  ";
	tree.PostOrder();
	cout << endl;

	//层序遍历
	cout << "层序遍历  ";
	tree.LevelOrder();
	cout << endl;


	cout << "树的深度 ";
	cout << tree.getTreeHight(tree.getRoot())<<endl;

	return 0;
}

运行结果：

二叉树的基本组成

结构体和类的构造和使用方法非常像，所以，在C++中，结构体也存在无参和有参构造；可以根据自己的需求来定义。

struct BiNode{
    int val;
    BiNode *lchild,*rchild;
    //BiNode() : val(0), lchild(nullptr), rchild(nullptr) {}
    // BiNode(int x) : val(x), lchild(nullptr), rchild(nullptr) {}
    // BiNode(int x, BiNode *lchild, BiNode *rchild) : val(x), lchild(lchild), rchild(rchild) {}
};

创建二叉树

这里我是通过队列的方式来创建二叉树的
每创建一个节点，就拿出一个数

void CreateTree(BiNode* &root,queue<int>& dp){   //通过队列创建二叉树
    if(dp.empty()) return ;
    int n=dp.front();
    dp.pop();
    if(n==0){   //等于0时，就是空节点
        return;
    }
    else{
        root =new BiNode();
        root->val=n;
        CreateTree(root->lchild,dp);
        CreateTree(root->rchild,dp);
    }
}

二叉树的4种常用遍历

先序遍历

void preOrder(BiNode* root){    //前序遍历
    if(root){
        cout<<root->val<<" ";
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
}

中序遍历

void inOrder(BiNode* root){    //中序遍历
    if(root!=NULL){        
        inOrder(root->lchild);
        cout<<root->val<<" ";
        inOrder(root->rchild);
    }
}

后序遍历

void postOrder(BiNode* root){    //后序遍历
    if(root){        
        postOrder(root->lchild);        
        postOrder(root->rchild);
        cout<<root->val<<" ";
    }
}

层序遍历

前面的三种先、中、后遍历方法，很常用，也很简单，基本上学会了其中一种，另外两种自然也就会了，只要调换一下位置就行了，原理非常简单；
第四种方法：层序遍历，也是非常的常用，使用的场景也很多，我这里是使用两重vector容器，把它的每一层都单独放在一起，在一般的做题或者其他场景，不需要这么细致的话，使用一维vector也是一样的。

vector<vector<int>> levelOrder(BiNode*& root) {  //层序遍历
    vector<vector<int>> res;
    if(root==NULL)  return res;   
    queue<BiNode*> dp;
    dp.push(root);

    while(!dp.empty()){  //如果队列为空，则已经遍历完毕
        int n=dp.size();    //获取队列的大小，也就是这一层的节点数
        res.push_back(vector<int> ());
        for(int i=1;i<=n;i++){  //每一次都把这一层的所有节点输出，遍历完这一层的，队列剩下的就是下一层的
            auto p=dp.front();dp.pop();
            res.back().push_back(p->val);
            if(p->lchild)     dp.push(p->lchild);   //把非空的节点加入队列
            if(p->rchild)    dp.push(p->rchild);
        }
    }
    return res;
}

在二叉树中查找值为val的节点

思路：
1、当root == NULL； return NULL;
2、当root->val ==num； return root;
3、当root->val!=num ； 则先去左子树中找,FindNode(root->lchild,num);
4、以上都不满足，则去右子树找

BiNode* FindNode(BiNode* &root,int num){
    BiNode* p;
    if(!root)   return NULL;	//节点为空
    else if (root->val==num)    return root;
    else{
        
        p=FindNode(root->lchild,num);
        if(p){
            return p;
        }
        else{
            return FindNode(root->rchild,num);
        }
    }
}

二叉树的高度（深度）

直接递归左右子树，比大小

int HeightTree(BiNode* root){
    if(!root)   return 0;
    return max(HeightTree(root->lchild),HeightTree(root->rchild))+1;
}

查找二叉树中的叶子节点

通过叶子节点性质，直接查找左右子节点都为空的节点，把它加入进vector数组

void FindLeaf(BiNode* &root,vector<BiNode*> &leafnode){
    if(root){
        if(!root->lchild && !root->rchild){
            leafnode.push_back(root);
            return;
        }
        if(root->lchild)    FindLeaf(root->lchild,leafnode);
        if(root->rchild)    FindLeaf(root->rchild,leafnode);
    }
}

以上就是本次介绍的关于二叉树的创建以及一些基本的使用

这是本次演示所使用的二叉树，下面附上一下演示的代码

#include<iostream>
#include<vector>
using namespace std;
#include<queue>

struct BiNode{
    int val;
    BiNode *lchild,*rchild;
    //BiNode() : val(0), lchild(nullptr), rchild(nullptr) {}
    // BiNode(int x) : val(x), lchild(nullptr), rchild(nullptr) {}
    // BiNode(int x, BiNode *lchild, BiNode *rchild) : val(x), lchild(lchild), rchild(rchild) {}
};

void CreateTree(BiNode* &root,queue<int>& dp);  //创建二叉树

void preOrder(BiNode* root);    //先序遍历
void inOrder(BiNode* root);     //中序遍历
void postOrder(BiNode* root);   //后序遍历
vector<vector<int>> levelOrder(BiNode*& root);  //层序遍历，一层层的输出

//template<class T> 
BiNode* FindNode(BiNode* &root,int val);    //查找值为val 的结点，找到了返回该节点地址，没找到则返回NULL
int HeightTree(BiNode* root);   //求二叉树的高度(深度)
void FindLeaf(BiNode* &root,vector<BiNode*> &leafnode);    //查找到叶子节点，并输出

//中间的函数在上面，就不再写了
int main(){
    BiNode* root;
    queue<int> dp;
    vector<int> arr={1,2,4,0,6,0,0,0,3,0,5,0,0};
    for(int i=0;i<arr.size();i++){
        dp.push(arr[i]);
    }
    //创建二叉树
    CreateTree(root,dp);
    
    //先、中、后三中遍历
    cout<<"preOrder: "<<endl;
    preOrder(root);
    cout<<"\ninOrder: "<<endl;
    inOrder(root);
    cout<<"\npostOrder: "<<endl;
    postOrder(root);
    cout<<"\nlevelOrder:  "<<endl;

	//层序遍历，一层层的输出
    vector<vector<int>> res=levelOrder(root);
    for(auto &ch:res){  //一层一层的输出
        for(auto &num:ch){
            cout<<num<<" ";
        }
        cout<<endl;
    }
	
	//查找指定节点，这里我是没有定义，直接给了一个固定值10，纯属是为了演示
    BiNode* findnode;
    findnode=FindNode(root,10);
    if(findnode){
        cout<<"findnode->val="<<findnode->val<<endl;
    }
    else{
        cout<<"This node does not exist in this binary tree! "<<endl;
    }
	
	//定义了一个ans,接收该二叉树的高度
    int ans=HeightTree(root);
    cout<<"The height of the binary tree is "<<ans<<endl;
	
	//查找该二叉树的叶子节点，并输出
    vector<BiNode*> leafnode(dp.size());
    FindLeaf(root,leafnode);
    for(auto& leaf:leafnode){
        cout<<leaf->val<<" ";
    }
    cout<<endl;
}

疑问，希望有大佬能够帮忙解惑！

以上便是我本次学习所得，不过有一个疑问，
在我用struct定义二叉树的基本结构的时候，如果我写了无参构造

BiNode() : val(0), lchild(nullptr), rchild(nullptr) {}

那么我在创建二叉树的时候，无论是

BiNode* root =new BiNode();

亦或是

BiNode* root =new BiNode;

都可以运行，且得出的答案都一样，
但如果我不写这个无参构造
那么第二种定义，在vscode中，虽然不会报错，但不会得出答案，便直接结束了。在网上找了很久，依然没有找到，希望有懂得大佬看到了能帮忙解惑，先谢谢了！

上述问题的原因

上述问题，在前一段时间困扰了我很久，一直没找到原因。
直到今天终于找到了，原来：
在自定义的数据类型中

1. 如果该类没有定义构造函数（由编译器合成默认构造函数）也没有虚函数，那么BiNode *root= new BiNode ;将不调用合成的默认构造函数，而BiNode *root = new BiNode ();则会调用默认构造函数。
2. 如果该类没有定义构造函数（由编译器合成默认构造函数）但有虚函数，那么BiNode *root= new BiNode ;和BiNode *root= new BiNode ();一样，都会调用默认构造函数。
3. 如果该类定义了默认构造函数，那么BiNode *root= new BiNode ;和BiNode *root= new BiNode ();一样，都会调用默认构造函数。

在内置的数据类型中，也是有区别的，但是因为现在还没有搞懂，所以就不写了。等以后明白了再回来补充！

二叉树的创建：

上篇文章遍历的时候二叉树的创建是这样的：

	TreeNode* T1 = new TreeNode(8);
	TreeNode* T2 = new TreeNode(8);
	TreeNode* T3 = new TreeNode(7);
	TreeNode* T4 = new TreeNode(9);
	TreeNode* T5 = new TreeNode(2);
	TreeNode* T6 = new TreeNode(4);
	TreeNode* T7 = new TreeNode(7);
	T1->left = T2; T1->right = T3; T2->left = T4; T2->right = T5; T3->left = T6; T3->right = T7;

显然这种创建方式很繁琐，当二叉树分枝不多的情况下可以这样创建，但是复杂的时候我们就需要一种方便简洁的创建方式。之所以没有先讲二叉树的创建是因为创建方式依靠的背景不一样。还记得前序遍，中序遍历和后序遍历没。一般二叉树的创建是依靠遍历创建的。

我们依照前序遍历的准则创建二叉树：
创建的二叉树如下图所示，#代表为空，因为我们定义的是int型而不是char型，故下面的代码把#看成0输入为空。

下面代码用了两种构建方式：
第一种的前序遍历如图；
前序遍历的方式输入：889002007400700

#include<iostream>
#include<queue>
using namespace std;
struct TreeNode {
	int data;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x):
		data(x),left(NULL),right(NULL){}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         
};
void preprintftree(TreeNode* root) {   //前序遍历
	if (root) {
		cout << root->data;    // 打印根结点
		preprintftree(root->left); // 前序遍历左子树
		preprintftree(root->right); // 前序遍历右子树
	}
	else
		root = NULL;
}
void preCreateTree(TreeNode* &T)  // 前序遍历创建二叉树，需要注意* &T目的是让传递进来的指针发生改变
{
	int data;
	cin >> data;
	if (data == 0)
	{
		T = nullptr;
	}
	else
	{
		T = new TreeNode(data); //构造结点
		preCreateTree(T->left);  //递归创建左子树
		preCreateTree(T->right); //递归创建右子树
	}
}
int main()
{
	TreeNode* T1 = new TreeNode(8);
	TreeNode* T2 = new TreeNode(8);
	TreeNode* T3 = new TreeNode(7);
	TreeNode* T4 = new TreeNode(9);
	TreeNode* T5 = new TreeNode(2);
	TreeNode* T6 = new TreeNode(4);
	TreeNode* T7 = new TreeNode(7);
	T1->left = T2; T1->right = T3; T2->left = T4; T2->right = T5; T3->left = T6; T3->right = T7;
	cout << "普通创建方式：" << endl;
	preprintftree(T1);
	cout << endl;
	TreeNode* Tree=nullptr;
	cout << "前序遍历创建方式：" << endl;
	preCreateTree(Tree);
	cout << "前序遍历结果：" << endl;
	preprintftree(Tree);
	return 0;
}

代码结果如下所示：

二叉树的重建

二叉树的创建讲完了，下面介绍二叉树的重建：
先了解：

	已知前序遍历和中序遍历可以确定唯一的二叉树；
	已知后序遍历和中序遍历可以确定唯一的二叉树；
	但是已知前序和后序不能确定。

已知二叉树的前序和中序，重建二叉树：

前序为：{ 1,2,4,7,3,5,6,8 }
中序为：{ 4,7,2,1,5,3,8,6 }
解题思路：
先序遍历规则：根节点==》左子树==》右子树

中序遍历规则：左子树==》根节点==》右子树

分析题目可知，二叉树中的节点值均是唯一的，不存在重复值。所以，
我们可以利用二叉树先序遍历和中序遍历特点，完成如下的工作：

Step1：确定根节点，即先序遍历preorder中的首个节点；
Step2：在中序遍历inorder中找到根节点的索引值index，以此为界，将中序遍历序列划分为
【左子树，根节点，右子树】，其中，左子树为索引值0至index，即inorder[0:index]，
右子树为index+1至中序遍历末尾元素，即inorder[index+1:]；
Step3：根据中序遍历序列中左右子树的节点数量，将先序遍历序列划分为【根节点，左子树，右子树】，
其中，左子树为索引值1至index+1，即preorder[1:index+1]，
右子树为index+1至先序遍历末尾元素，即preorder[index+1:]；
Step4：分别利用先序遍历和中序遍历中的左子树递归构造二叉树的左子树，
先序遍历和中序遍历中的右子树递归构造二叉树的右子树

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct treeNode {
    int data;
    treeNode* left;
    treeNode* right;
    treeNode(int x) :
        data(x),left(NULL), right(NULL) {}
};
treeNode* buildtree(vector<int>& pre, vector<int>& vin) {
    if (pre.size() == 0 || vin.size() == 0) return nullptr;
    int val = pre[0];
    treeNode* root = new treeNode(val);
    int index = 0;
    for (int i =0; i<vin.size(); i++)
        if (vin[i] == pre[0]) {
            index = i;
            break;
        }
    vector<int> preleft(pre.begin() + 1, pre.begin() + index+1);
    vector<int> vinleft(vin.begin() , vin.begin() + index);
    vector<int> preright(pre.begin() + index +1,pre.end());
    vector<int> vinright(vin.begin() + index +1,vin.end());
    root->left = buildtree(preleft, vinleft);
    root->right = buildtree(preright, vinright);
    return root;
}
void postprintfTree(treeNode* root) {
    if (root!=nullptr) {
        postprintfTree(root->left);
        postprintfTree(root->right);
        cout << root->data;
    }
    else {
        root = NULL;
    }
}
int main()
{
    vector<int>pre={ 1,2,4,7,3,5,6,8 };
    vector<int>vin={ 4,7,2,1,5,3,8,6 };
    treeNode* tree = buildtree(pre,vin);
    postprintfTree(tree); // 后序打印结果
    return 0;
}

判断二叉树是否为另一个二叉树的子树：

思路：
输入两个二叉树，判断其中的一个是否为另一个的子树：
1、首先设置标志位flag = false，因为一旦匹配成功flag就设为true，
剩下的代码不会执行，如果匹配不成功，默认返回false
2、递归思想，如果根节点相同则递归调用comparetree（），
如果根节点不相同，则判断tree1的左子树和tree2是否相同，
再判断右子树和tree2是否相同
3、注意null的条件，HasSubtree中，如果两棵树都不为空才进行判断，
comparetree中，如果Tree2为空，则说明第二棵树遍历完了，即匹配成功，
tree1为空有两种情况（1）如果tree1为空&&tree2不为空说明不匹配，
（2）如果tree1为空，tree2为空，说明匹配。

#include<iostream>
using namespace std;
struct treeNode {
	int data;
	treeNode* left;
	treeNode* right;
	treeNode(int x):
		data(x),left(NULL),right(NULL){}
};
bool comparetree(treeNode* s1, treeNode* s2) {
	if (s2 == nullptr) return true;
	if (s1 == nullptr) return false;
	if (s1->data != s2->data) return false;
	return comparetree(s1->left, s2->left) && comparetree(s1->right, s2->right);
}
bool HasSubtree(treeNode* root1, treeNode* root2)
{
	bool flag = false;
	if (root1 == nullptr || root2 == nullptr) return false;
	if (root1->data == root2->data) flag = comparetree(root1,root2);
 	if (!flag) flag = HasSubtree(root1->left,root2);
	if (!flag) flag = HasSubtree(root1->right, root2);
	return flag;
}
void preprintftree(treeNode* root) {
	if (root) {
		cout << root->data;
		preprintftree(root->left);
		preprintftree(root->right);
	}
	else
		root = NULL;
}
int main()
{
	treeNode* t1 = new treeNode(8);
	treeNode* t2 = new treeNode(8);
	treeNode* t3 = new treeNode(7);
	treeNode* t4 = new treeNode(9);
	treeNode* t5 = new treeNode(2);
	treeNode* t6 = new treeNode(4);
	treeNode* t7 = new treeNode(7);
	t1->left = t2; t1->right = t3; t2->left = t4; t2->right = t5; t3->left = t6; t3->right = t7;
	treeNode* tt1 = new treeNode(8);
	treeNode* tt2 = new treeNode(9);
	treeNode* tt3 = new treeNode(2);
	tt1->left = tt2; tt1->right = tt3;
	preprintftree(t1);
	cout << endl;
	preprintftree(tt1);
	cout << endl;
	bool res = HasSubtree(t1, tt1);
	cout << res << endl;
	return 0;
}

二叉树的镜像

这个其实很简单，和swap原理一样。
核心代码：

思路：左右分枝对换就行了;
TreeNode* Mirror(TreeNode* pRoot) {
	if (pRoot == nullptr) return pRoot;
	TreeNode* temp;
	temp = pRoot->left;
	pRoot->left = pRoot->right;
	pRoot->right = temp;
	Mirror(pRoot->left);
	Mirror(pRoot->right);
	return pRoot;
}

总的代码：

#include<iostream>
using namespace std;
struct TreeNode {
	int data;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x):
		data(x),left(NULL),right(NULL){}
};
TreeNode* Mirror(TreeNode* pRoot) {
	if (pRoot == nullptr) return pRoot;
	TreeNode* temp;
	temp = pRoot->left;
	pRoot->left = pRoot->right;
	pRoot->right = temp;
	Mirror(pRoot->left);
	Mirror(pRoot->right);
	return pRoot;
}
void preprintftree(TreeNode* root) {
	if (root) {
		cout << root->data;
		preprintftree(root->left);
		preprintftree(root->right);
	}
	else
		root = NULL;
}
int main()
{
	TreeNode* T1 = new TreeNode(8);
	TreeNode* T2 = new TreeNode(8);
	TreeNode* T3 = new TreeNode(7);
	TreeNode* T4 = new TreeNode(9);
	TreeNode* T5 = new TreeNode(2);
	TreeNode* T6 = new TreeNode(4);
	TreeNode* T7 = new TreeNode(7);
	T1->left = T2; T1->right = T3; T2->left = T4; T2->right = T5; T3->left = T6; T3->right = T7;
	preprintftree(T1);
	cout << endl;
	TreeNode* p = Mirror(T1);
	preprintftree(p);
	return 0;
}

判断二叉树是否对称

由于上面给出了很多二叉树的测试用例，下面介绍的功能函数直接放核心代码函数接口：

bool isSame(TreeNode* p1,TreeNode* p2)
    {
        if(p1==NULL&&p2!=NULL)return false;
        if(p2==NULL&&p1!=NULL)return false;
        if(p1==NULL&&p2==NULL)return true;
        if(p1->val==p2->val)return isSame(p1->right,p2->left)
            && isSame(p1->left,p2->right);
        else
            return false;
    }
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==NULL)return true;        
        return isSame(pRoot->left,pRoot->right);
    }

求二叉树的深度：

思路：
从跟节点出发， 查询左子树的深度 ， 获取右子树的深度，比较一下，取大的，再加一 。就是整个二叉树的深度
递归的三个条件
边界条件：当前节点下，是否还有子节点，没有返回，有继续递归
递归前进段：当前节点下，还有子节点
递归返回段：当前节点下，没有子节点

int TreeDepth1(TreeNode pRoot)
    {
        if(pRoot == null){
            return 0;
        }
        int left = TreeDepth1(pRoot.getLeft());
        int right = TreeDepth1(pRoot.getRight());
        return Math.max(left, right) + 1;
    }

为了便于理解，请看下图：

二叉树是否为平衡二叉树：

平衡二叉树的定义：如果二叉树的每个节点的左子树和右子树的深度不大于1，它就是平衡二叉树。
思路：
最直接的做法，遍历每个结点，借助一个获取树深度的递归函数，根据该结点的左右子树高度差判断是否平衡，然后递归地对左右子树进行判断。

public classSolution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null) {
            return true;
        }
        return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 &&
            IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    private int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

这种做法有很明显的问题，在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销。如果改为从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return getDepth(root) != -1;
    }
    private int getDepth(TreeNode root) {
        if (root == null) return 0;
        int left = getDepth(root.left);
        if (left == -1) return -1;
        int right = getDepth(root.right);
        if (right == -1) return -1;
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
}