leetcode-二叉搜索树-BST-【中序遍历 、升序遍历、降序遍历】_二叉树哪种遍历方式可以得到降序输出

2022年10月27日 14点18分

• 对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。
• 对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST
• BST 的中序遍历结果是有序的 230. 二叉搜索树中第K小的元素

二叉搜索树并不算复杂，但它可以算是数据结构领域的半壁江山，直接基于 BST 的数据结构有 AVL 树，红黑树等等，拥有了自平衡性质，可以提供 logN 级别的增删查改效率；还有 B+ 树，线段树等结构都是基于 BST 的思想来设计的

// 二叉树升序遍历
void traverse(TreeNode root) {
    if (root == null) return;
    traverse(root.left);
    // 中序遍历代码位置
    print(root.val);
    traverse(root.right);
}
// 二叉树降序遍历
void traverse(TreeNode root) {
    if (root == null) return;
    // 先递归遍历右子树
    traverse(root.right);
    // 中序遍历代码位置
    print(root.val);
    // 后递归遍历左子树
    traverse(root.left);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

BST降序遍历

538. 把二叉搜索树转换为累加树

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.sum = 0
        self.traverse(root)
        return root

    def traverse(self,root):
        if not root:return
        self.traverse(root.right)
        self.sum += root.val
        root.val = self.sum
        self.traverse(root.left)
1
2
3
4
5
6
7
8
9
10
11
12