前言今天来说说二叉树。树先看看什么是树？？。如图所示，这个有节点的结构就是一棵树。树是n(n>=0)个节点的有限集。每个元素称为一个节点。上一节是下一节的父节点。比如1是2的父节点的最顶层节点，也就是没有父节点的节点的节点称为根节点，如1，同父节点的节点称为兄弟节点，如2、3、4为兄弟节点，没有子节点的节点称为叶节点。一棵分叉的树但是并不要求必须有两个节点，只要数量小于或等于2个节点即可。比如这种：其中，可以看到绿树的每个节点都有左右两个节点。这种二叉树称为满二叉树。还有另一种二叉树，称为完全二叉树。完全二叉树：对一棵有n个节点的二叉树逐层编号，如果第i个节点（1<=i<=n）和同一深度的完全二叉树中第i个节点在二叉树位置恰好一样，那么这棵二叉树就称为完全二叉树。这是什么意思？比如满二叉树，每个节点都是按顺序编号的。如果去掉一些节点，编号不变，那么就是一棵完全二叉树。例如：在这张图中，绿树是一棵满二叉树。当节点7被移除时，它变成了一棵黄色的树。这棵黄树的序号和满二叉树的序号一一对应，所以这棵黄树是一棵完全二叉树。如果节点6被移除并成为红树，那么红树的节点必须改变。6消失后，节点7必须变成节点6才正确。所以这棵红树不是完全二叉树，因为它相对于完全二叉树的序号发生了变化，不能再对应了。算法——平衡二叉树说了这么多，该出一道题来练习了。输入一棵二叉树的根节点，判断该树是否为平衡二叉树。如果一棵二叉树中任意一个节点的左右子树的深度差不超过1，那么它就是一棵平衡二叉树。示例1：给定一棵二叉树[3,9,20,null,null,15,7]3/\920/\157返回true。解析题目给出了平衡二叉树的概念，即任意节点的左右子树之差不超过1，就是平衡二叉树。那么这个深度是多少？深度是从根节点到当前节点的边数。\23深度1，层数2/\45深度2，层数3解法1首先想到的是计算每个节点的深度，然后比较左右节点是否是平衡二叉树。那么如何计算一个节点的子树深度呢？递归。子节点为空时返回，否则每次增加一个单位的深度。/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(intx){val=x;}*}*/privateintdepth(TreeNoderoot){if(root==null)return0;returnMath.max(depth(root.left),depth(root.right))+1;}一旦确定了深度，这道题就很好解决了，就是遍历每个节点的左右深度，还是需要递归:classSolution{publicbooleanisBalanced(TreeNoderoot){if(root==null)返回真；returnMath.abs(depth(root.left)-depth(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);}privateintdepth(TreeNoderoot){if(root==null)return0;returnMath.max(depth(root.left),depth(root.right))+1;}}从根节点开始，计算每个左子树和右子树的深度差，以及左子树的深度和下面每个节点的右子树，最后得到结果。这种先处理节点，再处理左子树，再处理右子树的遍历方式称为前序遍历或前序遍历。时间复杂度假设节点总数为n，层数为x，二叉树为满二叉树。时间复杂度计算可以通过每一层的时间复杂度*层复杂度来计算每一层的时间复杂度：第一层需要遍历n次，第二层需要遍历n-1次，第三层需要遍历n-3次，所以每一层的时间复杂度为O(n)层复杂度：第一层1个节点，第二层2个节点，第三层4个节点，第x层是2x-1的幂。借助公式：n>=1+2+4+8+...+2^(x-2)+1n<=1+2+4+8+...+2^(L-2)+2^(L-1)计算：n>=1+2+4+8+...+2^(x-2)+1n>=(2^(x-1)-1)+1n>=2^(x-1)x<=log2n+1同理：x>=log2(n+1)，所以一棵近平衡二叉树的高度（层数）接近于logn。所以总的时间复杂度是O(nlogn)空间复杂度。既然用到了递归，又用到了栈帧，前面说了和最大递归深度成正比，所以空间复杂度是O(n)解法2，有没有更好的解法？解决方案呢？刚才我们用的是前序遍历，但是可以发现每个节点都会计算一次深度，而且会有很多重复的计算，那我们可以试试不重复的算法？比如直接后序遍历。后序遍历：对于任意节点，先处理左子树，再处理右子树，最后处理节点本身。计算深度还是用刚才的方法：privateintdepth(TreeNoderoot){if(root==null)return0;intleft=recur(root.left);intright=recur(root.right);returnMath.max(left,right)+1;}如果可以计算出左子树的深度和右子树的深度，那我们就可以直接比较了。如果发现一个节点的左子树深度和右子树深度之差大于1，那么我们可以直接返回false。所以可以综合得到第二个解：(left==-1)return-1;intright=recur(root.right);if(right==-1)return-1;returnMath.abs(left-right)<2?Math.max(left,right)+1:-1;}}时间复杂度n为节点总数，遍历所有节点，所以时间复杂度为O(n)空间复杂度O(n)参考https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/https://time.geekbang.org/column/article/67856本文转载自微信公众号《代码积木》，可关注以下二维码代码。转载本文请联系代码上的积木公众号。
