求高求深，你懂吗？平衡二叉树题目地址：https://leetcode-cn.com/problems/balanced-binary-tree/给定一个二叉树，判断它是否是高度平衡的二叉树。本题对一棵高度平衡二叉树的定义为：一棵二叉树每个节点的左右子树高度差的绝对值不超过1。例1：给定一棵二叉树[3,9,20,null,null,15,7]返回true。示例2：给定二叉树[1,2,2,3,3,null,null,4,4]返回false。题外话这个题目乍一看和104.二叉树的最大深度很像，其实还是有很大区别的。这里强调一波概念：二叉树节点的深度：是指从根节点到该节点的最长简单路径边的条数。二叉树节点的高度：是指从该节点到叶节点的最长简单路径边的数量。但是leetcode中强调的深度和高度，明显是按照节点计算的，如图：根节点的深度是1还是0，不同的地方有不同的标准，leetcode的题目是根据节点，即根节点的深度为1。但是维基百科将一条边定义为1度，即根节点的深度为0，我们暂时以leetcode为标准（毕竟需要写上面的问题）。因为可以从上到下查深度，所以需要前序遍历（中、左、右），而只能从下到上查高度，所以只能后序遍历（左、右、中）肯定有同学疑惑为什么104.BinarytreeThemaximumdepth就是二叉树的最大深度，还用到了后序遍历。那是因为代码的逻辑其实就是求根节点的高度，而根节点的高度就是树的最大深度，所以可以使用后序遍历。104.二叉树的最大深度，如果真的得到二叉树的最大深度，代码应该这样写：（前序遍历）classSolution{public:intresult;voidgetDepth(TreeNode*node,intdepth){result=depth>result?depth:result;//middleif(node->left==NULL&&node->right==NULL)return;if(node->left){//leftdepth++;//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;}};可见前序（左右）的遍历使用的是Order，这才是真正的求深逻辑！请注意，上面的代码是为了反映细节。简化代码如下：return;if(node->left){//leftgetDepth(node->left,depth+1);}if(node->right){//rightgetDepth(node->right,depth+1);}return;}intmaxDepth(TreeNode*root){result=0;if(root==0)returnresult;getDepth(root,1);返回结果；}}；这道题的思路是递归的。这时候大家应该明白了，既然要求比较高，那肯定是后序遍历。递归三部曲分析：如果指定了递归函数的参数和返回值参数，就是传递的节点指针，不需要传递其他参数。返回值应该返回传递的节点为根节点的树的深度。那么如何标记左右子树的差值是否大于1呢？如果当前输入节点为根节点的二叉树不再是二叉平衡树，返回高度就没有意义了。所以如果不再是二叉平衡树，可以返回-1来标记不符合平衡树的规则。代码如下：//-1表示不再是平衡二叉树，否则返回值以该节点为根节点树的高度intgetDepth(TreeNode*node)来指定终止条件。在递归过程中，它仍然遇到一个空节点作为终止。返回0，表示当前节点作为根节点的树高为0，代码如下：if(node==NULL){return0;}清除单级递归的逻辑如何判断是否为二进制当前入节点为根节点的树是平衡二叉树吗？，当然是左子树的高度和右子树的高度之差。分别求左右子树的高度，如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示不再是二叉树。代码如下：intleftDepth=depth(node->left);//leftif(leftDepth==-1)return-1;intrightDepth=depth(node->right);//rightif(rightDepth==-1)return-1;intresult;if(abs(leftDepth-rightDepth)>1){//中间结果=-1;}else{result=1+max(leftDepth,rightDepth);//当前最大高度node作为根节点}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(节点->右);如果（右深度==-1）返回-1；returnabs(leftDepth-rightDepth)>1?-1:1+max(leftDepth,rightDepth);}最后这道题的整体递归代码如下：classSolution{public://返回二叉树的高度with以该节点为根节点，如果不是二叉搜索树，则返回-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;}};IterationIn104.在二叉树的最大深度中，我们可以用层序遍历求深度，但是不能直接用层序遍历求高度，体现的是高度和深度的区别。这道题的迭代法可以先定义一个函数，专门用来求高度的。该函数通过栈模拟的后序遍历求出每个节点的高度（其实高度是通过求传入节点的最大深度为根节点得到的）。代码如下：//cur节点的最大深度为cur的高度intgetDepth(TreeNode*cur){stackst;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);//rightif(node->left)st.push(node->left);//left}else{st.pop();node=st.top();st.pop();depth--;}result=result>depth?result:depth;}returnresult;}然后用栈来模拟前序遍历。遍历每个节点时，判断左右孩子的高度是否符合，代码如下：boolisBalanced(TreeNode*root){stackst;if(root==NULL)returntrue;st.push(root);while(!st.empty()){TreeNode*node=st.top();//middlest.pop();if(abs(getDepth(node->left)-getDepth(node->right))>1){//判断左右孩子的高度是否满足returnfalse;}if(node->right)st.push(node->right);//right（空节点不入栈）if(node->left)st.push(node->left);//left（空节点不入栈）stack)}returntrue;}整体代码如下：classSolution{private:intgetDepth(TreeNode*cur){stackst;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);//left}else{st.pop();node=st.top();st.pop();depth--;}result=result>depth?result:depth;}returnresult;}public:boolisBalanced(TreeNode*root){stackst;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);//right(空节点不入栈)if(node->left)st.push(node->left);//left(空节点不入栈)压入堆栈）}returntrue;}};当然这道题用的是迭代法，但是效率其实很低，因为没有很好的模拟回溯过程，所以迭代法有很多重复计算。虽然理论上所有的递归都可以通过迭代来实现，但是有些场景可能会比较难。例如：我们都知道回溯法其实就是递归，但是很少有人用迭代的方式来实现回溯算法！因为回溯算法已经是很复杂的递归了，如果再用迭代，就是给自己找麻烦，效率也低。它不必很高。小结通过这道题，可以理解二叉树的深度和二叉树的高度的区别。深度适合前序遍历，高度适合后序遍历。这道题的迭代方法其实有点复杂。你可以有一个想法，并不一定意味着你必须把它写出来。但是递归的方法一定要掌握！其他语言版本JavaclassSolution{/***递归方法*/publicbooleanisBalanced(TreeNoderoot){returngetHeight(root)!=-1;}privateintgetHeight(TreeNoderoot){if(root==null){return0;}intleftHeight=getHeight(root.left);if(leftHeight==-1){return-1;}intrightHeight=getHeight(root.right);if(rightHeight==-1){return-1;}//左右高度差subtrees大于1，return-1表示不再是平衡树if(Math.abs(leftHeight-rightHeight)>1){return-1;}returnMath.max(leftHeight,rightHeight)+1;}}classSolution{/***迭代法，效率低，计算高度时重复遍历*时间复杂度：O(n^2)*/publicbooleanisBalanced(TreeNoderoot){if(root==null){returntrue;}Stackstack=newStack<>();TreeNodepre=null;while(root!=null||!stack.isEmpty()){while(root!=null){stack.push(root);root=root.left;}TreeNodeinNode=stack.peek();//右节点为null或者已经遍历过if(inNode.right==null||inNode.right==pre){//比较左右子树高度差并输出if(Math.abs(getHeight(inNode.left)-getHeight(inNode.right))>1){returnfalse;}stack.pop();pre=inNode;root=null;//当前节点下，不需要遍历的节点没有了}else{root=inNode.right;//右边的节点还没有遍历，遍历右节点}}returntrue;}/***层序遍历，求节点的高度*/publicintgetHeight(TreeNoderoot){if(root==null){return0;}dequedeque=newLinkedList<>();deque.offer(root);intdepth=0;while(!deque.isEmpty()){intsize=deque.size();depth++;for(inti=0;istack=newStack<>();TreeNodepre=null;while(root!=null||!stack.isEmpty()){while(root!=null){stack.push(root);root=root.left;}TreeNodeinNode=stack.peek();//右节点为null或者已经遍历if(inNode.right==null||inNode.right==pre){//输出if(Math.abs(getHeight(inNode.left)-getHeight(inNode.right))>1){returnfalse;}stack.pop();pre=inNode;root=null;//当前节点下，没有要遍历的节点}else{root=inNode.right;//右节点还没遍历，遍历右节点}}returntrue;}/***求节点的高度*/publicintgetHeight(TreeNoderoot){if(root==null){return0;}intleftHeight=root.left!=null?root.left.val:0;intrightHeight=root.right!=null?root.right.val:0;intheight=Math.max(leftHeight,rightHeight)+1;root.val=height;//用TreeNode.val保存当前节点的高度returnheight;}}Python递归方法：classSolution:defisBalanced(self,root:TreeNode)->bool:returnTrueifself.getDepth(root)!=-1elseFalse#返回以该节点为根节点的二叉树的高度，如果是不是二叉搜索树，返回-1defgetDepth(self,node):ifnotnode:return0leftDepth=self.getDepth(node.left)ifleftDepth==-1:return-1#表示左子树不再是二叉平衡树rightDepth=self.getDepth(node.right)ifrightDepth==-1:return-1#表示右子树不再是二叉平衡树return-1ifabs(leftDepth-rightDepth)>1else1+max(leftDepth,rightDepth)迭代方法：classSolution:defisBalanced(self,root:TreeNode)->bool:st=[]ifnotroot:returnTruest。append(root)whilest:node=st.pop()#中ifabs(self.getDepth(node.left)-self.getDepth(node.right))>1:returnFalseifnode.right:st.append(node.right)#Right（空节点不堆叠）ifnode.left:st.append(node.left)#Left（空节点不堆叠）returnTruedefgetDepth(self,cur):st=[]ifcur:st.append(cur)depth=0result=0whilest:node=st.pop()ifnode:st.append(node)#中st.append(None)depth+=1ifnode.right:st.append(node.right)#rightifnode.left:st.append(node.left)#leftelse:node=st.pop()depth-=1result=max(result,depth)返回结果
