平不平衡看高度，注意不是深度。110.平衡二叉树给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树界说为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不凌驾1。

示例 1:给定二叉树 [3,9,20,null,null,15,7]返回 true。示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4]返回 false。题外话咋眼一看这道题目和二叉树：看看这些树的最大深度很像，其实有很大区别。这里强调一波观点：二叉树节点的深度：指从根节点到该节点的最长简朴路径边的条数。

二叉树节点的高度：指从该节点到叶子节点的最长简朴路径边的条数。但leetcode中强调的深度和高度很显着是根据节点来盘算的，如图：关于根节点的深度究竟是1 还是 0，差别的地方有纷歧样的尺度，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上界说用边为一度，即根节点的深度是0，我们暂时以leetcode为准（究竟要在这上面刷题）。

因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）有的同学一定疑惑，为什么二叉树：看看这些树的最大深度 中求的是二叉树的最大深度，也用的是后序遍历。「那是因为代码的逻辑其实是求的根节点的高度，而根节点的高度就是这颗树的最大深度，所以才可以使用后序遍历。

」在二叉树：看看这些树的最大深度 中，如果真正求取二叉树的最大深度，代码应该写成如下：（前序遍历）classSolution{public:intresult;voidgetDepth(TreeNode*node,intdepth){result=depth>result?depth:result;//中if(node->left==NULL&&node->right==NULL)return;if(node->left){//左depth++;//深度+1getDepth(node->left,depth);depth--;//回溯，深度-1}if(node->right){//右depth++;//深度+1getDepth(node->right,depth);depth--;//回溯，深度-1}return;}intmaxDepth(TreeNode*root){result=0;if(root==0)returnresult;getDepth(root,1);returnresult;}};「可以看出使用了前序（中左右）的遍历顺序，这才是真正求深度的逻辑！」注意以上代码是为了把细节体现出来，简化一下代码如下：classSolution{public:intresult;voidgetDepth(TreeNode*node,intdepth){result=depth>result?depth:result;//中if(node->left==NULL&&node->right==NULL)return;if(node->left){//左getDepth(node->left,depth+1);}if(node->right){//右getDepth(node->right,depth+1);}return;}intmaxDepth(TreeNode*root){result=0;if(root==0)returnresult;getDepth(root,1);returnresult;}};本题思路递归此时大家应该明确了既然要求比力高度，一定是要后序遍历。递归三步曲分析：明确递归函数的参数和返回值参数的话为传入的节点指针，就没有其他参数需要通报了，返回值要返回传入节点为根节点树的深度。

那么如何标志左右子树是否差值大于1呢。如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。

所以如果已经不是二叉平衡树了，可以返回-1 来标志已经不切合平衡树的规则了。代码如下：//-1表现已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度intgetDepth(TreeNode*node)明确终止条件递归的历程中依然是遇到空节点了为终止，返回0，表现当前节点为根节点的高度为0代码如下：if(node==NULL){return0;}明确单层递归的逻辑如何判断当前传入节点为根节点的二叉树是否是平衡二叉树呢，固然是左子树高度和右子树高度相差。划分求出左右子树的高度，然后如果差值小于即是1，则返回当前二叉树的高度，否则则返回-1，表现已经不是二叉树了。

代码如下：intleftDepth=depth(node->left);//左if(leftDepth==-1)return-1;intrightDepth=depth(node->right);//右if(rightDepth==-1)return-1;intresult;if(abs(leftDepth-rightDepth)>1){//中result=-1;}else{result=1+max(leftDepth,rightDepth);//以当前节点为根节点的最大高度}returnresult;代码精简之后如下：intleftDepth=getDepth(node->left);if(leftDepth==-1)return-1;intrightDepth=getDepth(node->right);if(rightDepth==-1)return-1;returnabs(leftDepth-rightDepth)>1?-1:1+max(leftDepth,rightDepth);此时递归的函数就已经写出来了，这个递归的函数传入节点指针，返回以该节点为根节点的二叉树的高度，如果不是二叉平衡树，则返回-1。getDepth整体代码如下：intgetDepth(TreeNode*node){if(node==NULL){return0;}intleftDepth=getDepth(node->left);if(leftDepth==-1)return-1;intrightDepth=getDepth(node->right);if(rightDepth==-1)return-1;returnabs(leftDepth-rightDepth)>1?-1:1+max(leftDepth,rightDepth);}最后本题整体递归代码如下：classSolution{public://返回以该节点为根节点的二叉树的高度，如果不是二叉搜索树了则返回-1intgetDepth(TreeNode*node){if(node==NULL){return0;}intleftDepth=getDepth(node->left);if(leftDepth==-1)return-1;//说明左子树已经不是二叉平衡树intrightDepth=getDepth(node->right);if(rightDepth==-1)return-1;//说明右子树已经不是二叉平衡树returnabs(leftDepth-rightDepth)>1?-1:1+max(leftDepth,rightDepth);}boolisBalanced(TreeNode*root){returngetDepth(root)==-1?false:true;}};迭代在二叉树：看看这些树的最大深度中我们可以使用层序遍向来求深度，可是就不能直接用层序遍向来求高度了，这就体现出求高度和求深度的差别。

本题的迭代方式可以先界说一个函数，专门用来求高度。这个函数通过栈模拟的后序遍历找每一个节点的高度（其实是通过求传入节点为根节点的最大深度来求的高度）代码如下：//cur节点的最大深度，就是cur的高度intgetDepth(TreeNode*cur){stack<TreeNode*>st;if(cur!=NULL)st.push(cur);intdepth=0;//记载深度intresult=0;while(!st.empty()){TreeNode*node=st.top();if(node!=NULL){st.pop();st.push(node);//中st.push(NULL);depth++;if(node->right)st.push(node->right);//右if(node->left)st.push(node->left);//左}else{st.pop();node=st.top();st.pop();depth--;}result=result>depth?result:depth;}returnresult;}然后再用栈来模拟前序遍历，遍历每一个节点的时候，再去判断左右孩子的高度是否切合，代码如下：boolisBalanced(TreeNode*root){stack<TreeNode*>st;if(root==NULL)returntrue;st.push(root);while(!st.empty()){TreeNode*node=st.top();//中st.pop();if(abs(getDepth(node->left)-getDepth(node->right))>1){//判断左右孩子高度是否切合returnfalse;}if(node->right)st.push(node->right);//右（空节点不入栈）if(node->left)st.push(node->left);//左（空节点不入栈）}returntrue;}整体代码如下：classSolution{private:intgetDepth(TreeNode*cur){stack<TreeNode*>st;if(cur!=NULL)st.push(cur);intdepth=0;//记载深度intresult=0;while(!st.empty()){TreeNode*node=st.top();if(node!=NULL){st.pop();st.push(node);//中st.push(NULL);depth++;if(node->right)st.push(node->right);//右if(node->left)st.push(node->left);//左}else{st.pop();node=st.top();st.pop();depth--;}result=result>depth?result:depth;}returnresult;}public:boolisBalanced(TreeNode*root){stack<TreeNode*>st;if(root==NULL)returntrue;st.push(root);while(!st.empty()){TreeNode*node=st.top();//中st.pop();if(abs(getDepth(node->left)-getDepth(node->right))>1){returnfalse;}if(node->right)st.push(node->right);//右（空节点不入栈）if(node->left)st.push(node->left);//左（空节点不入栈）}returntrue;}};固然此题用迭代法，其实效率很低，因为没有很好的模拟回溯的历程，所以迭代法有许多重复的盘算。虽然理论上所有的递归都可以用迭代来实现，可是有的场景难度可能比力大。「例如：都知道回溯法其实就是递归，可是很少人用迭代的方式去实现回溯算法！」因为对于回溯算法已经是很是庞大的递归了，如果在用迭代的话，就是自己给自己找贫苦，效率也并纷歧定高。

总结通过本题可以相识求二叉树深度 和 二叉树高度的差异，求深度适适用前序遍历，而求高度适适用后序遍历。本题迭代法其实有点庞大，大家可以有一个思路，也纷歧定说非要写出来。可是递归方式是一定要掌握的！-------end-------我将算法学习相关的资料已经整理到了Github ：https://github.com/youngyangyang04/leetcode-master，内里另有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图，可以fork到自己堆栈有空看一看一定会有所收获，顺便给一个star支持一下吧！我是法式员Carl，哈工大师兄，先后在和百度打杂，这里天天8:35准时推送一道经典算法题目，我选择的每道题目都不是伶仃的，而是由浅入深，环环相扣，帮你梳理算法知识脉络，轻松学算法！@代码随想录 期待你的关注。

本文来源：完美体育-www.business365.cn