前言：
而今看官们对“求二叉树高度算法”大概比较关怀，同学们都想要了解一些“求二叉树高度算法”的相关资讯。那么小编同时在网摘上汇集了一些关于“求二叉树高度算法””的相关知识，希望咱们能喜欢，看官们一起来学习一下吧！请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 1
示例输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]限制0 <= 节点个数 <= 1000方法一：递归
一点点经验：每次看到有关树的算法的时候，我脑海里第一个想到的都是“先试试用递归可不可以”，阅读完题目后发现，no problem！
从根节点开始，递归遍历整个二叉树，交换每个节点的左/右子节点，就生成它的镜像了。
算法流程：
如果为空（即遍历叶子节点），直接返回null；旋转，递归左/右子节点；并将返回值作为当前节点的右/左子节点；返回当前节点。
代码如下：
复杂度分析时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。方法二：辅助栈（或队列）
利用栈（或队列）遍历树的所有节点，并交换每个节点的左/右子节点。
算法流程：
如果为空（即遍历叶子节点），直接返回null；把根节点加入到栈（或队列）中；弹出栈（或队列）中的根节点（当前节点）；如果左/右子节点非空，将左/右子节点入栈（或队列）；交换当前节点的左/右子节点；当栈（或队列）为空时返回根节点。
代码如下：
复杂度分析时间复杂度：O(N)，其中 N 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N) 时间。空间复杂度：O(N)，最差情况下，栈 stack 最多同时存储
(N+1)/2 个节点，占用 O(N) 额外空间。
END
递归是自下而上交换，栈是自上而下交换。
本文内容出处是力扣官网，希望和大家一起刷算法，在后面的路上不变秃但是变强！
好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。
标签： #求二叉树高度算法
