平衡二叉树中序遍历得到降序序列
平衡二叉树（AVL树）是一种自平衡的二叉搜索树。它保证搜索、插入和删除操作的时间复杂度均为O(logn)。其中，平衡二叉树中序遍历得到的序列是有序的，但是如果要得到降序序列，需要有一定的操作步骤。
一、什么是平衡二叉树
平衡二叉树是一种特殊的二叉搜索树，它的左子树和右子树的高度差不超过1，也就是说任何一个节点的左右子树的高度差都不超过1。在一个非平衡的二叉搜索树中，搜索的时间复杂度可能达到O(n)，而在平衡二叉树中搜索的时间复杂度为O(logn)。
二、平衡二叉树的特性
平衡二叉树的特性决定了它可用于多种场合。以下是平衡二叉树的特性：
1. 搜索、插入、删除操作的时间复杂度均为O(logn)，效率较高。
2. 平衡二叉树是一种自平衡的数据结构。当节点的插入或删除引起了树在某个节点处失衡，平衡二叉树会通过一系列操作来重新调整节点间的平衡，以保证树的平衡性。
3. 平衡二叉树可以用于排序、优先队列、哈希表等多种数据结构中，可广泛应用于计算机系统中。
三、平衡二叉树中序遍历得到升序序列
在平衡二叉树上进行中序遍历得到的序列是升序序列。升序序列有时候并不是我们需要的，如果需要得到降序序列，需要对升序序列进行逆序输出。
以下是平衡二叉树中序遍历得到逆序输出的代码实现：
```java
void inorderTraversalReversed(TreeNode root) {
if(root == null) {
return;
}
Stack
TreeNode cur = root;
while(cur!=null || !stack.empty()) {
while(cur!=null) {
stack.push(cur);
cur = cur.right; //只有这里与中序遍历相比，其他地方完全一样
}
cur = stack.pop();
System.out.print(cur.val + " ");
cur = cur.left;
}
}
```
四、平衡二叉树中序遍历得到降序序列
在平衡二叉树中，如果要得到降序序列，可以通过以下步骤实现：
1. 将根节点入栈。
2. 只要栈不空，取出栈顶元素并输出。如果栈顶元素有右孩子，则将右孩子入栈。将左孩子入栈。循环执行该步骤。
以下是平衡二叉树中序遍历得到降序序列的代码实现：
```java
void inorderTraversalReversed(TreeNode root) {
if(root == null) {
return;
}
Stack
TreeNode cur = root;
while(cur!=null || !stack.empty()) {
while(cur!=null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
System.out.print(cur.val + " ");
cur = cur.right; //只有这里与中序遍历相比，其他地方完全一样
}
}
```
