BST inorder traverse

对于一个BST，参考98题给出的定义：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树

直接基于 BST 的数据结构有 AVL 树，红黑树等等，拥有了自平衡性质，可以提供 logN 级别的增删查改效率；还有 B+ 树，线段树等结构都是基于 BST 的思想来设计的。

从做算法题的角度来看 BST，除了它的定义，还有一个重要的性质：BST 的中序遍历结果是有序的（升序）。

中序遍历一个bst的基本范式如下：

function traverse(root) {
    if (root == null) return;
    traverse(root.left);
    // do something
    callback(root.val);
    traverse(root.right);
}

典型的题目如下：

230. Kth Smallest Element in a BST

source: https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Question

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

思路

中序遍历, 然后数组找出index=k-1的元素。

pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
    if root.is_none() {
        return k;
    }
    fn dfs(root: Option<Rc<RefCell<TreeNode<i32>>>>, ret: &mut Vec<i32>) {
        if let Some(root) = root {
            let left = root.borrow_mut().left.take();
            let right = root.borrow_mut().right.take();
            dfs(left, ret);
            ret.push(root.borrow().val);
            dfs(right, ret);
        }
    }
    let mut list = vec![];
    dfs(root, &mut list);
    *list.get(k as usize - 1).unwrap()
}

538. Convert BST to Greater Tree

source: https://leetcode.com/problems/convert-bst-to-greater-tree/

Question

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

思路

中序遍历后等于排序，列表里推入node，然后把node的值改为累加值

pub fn convert_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    if root.is_none() {
        return root;
    }
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, ret: &mut Vec<Rc<RefCell<TreeNode>>>) {
        if let Some(root) = root {
            let left = root.borrow_mut().left.clone();
            let right = root.borrow_mut().right.clone();
            dfs(&left, ret);
            ret.push(root.clone());
            dfs(&right, ret);
        }
    }
    let mut list = vec![];
    dfs(&root, &mut list);
    let mut acc = 0;
    while let Some(node) = list.pop() {
        let val = node.borrow_mut().val;
        node.borrow_mut().val = acc + val;
        acc += val;
    }
    root
}

1038. Binary Search Tree to Greater Sum Tree

source: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Question

思路

还是根据BST的中序遍历是从小到大的顺序，替换掉val值。

pub fn bst_to_gst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    if root.is_none() {
        return root;
    }
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, ret: &mut Vec<Rc<RefCell<TreeNode>>>) {
        if let Some(root) = root {
            let left = root.borrow_mut().left.clone();
            let right = root.borrow_mut().right.clone();
            dfs(&left, ret);
            ret.push(root.clone());
            dfs(&right, ret);
        }
    }
    let mut list = vec![];
    dfs(&root, &mut list);
    let mut sum = 0;
    while let Some(node) = list.pop() {
        let val = node.borrow_mut().val;
        sum += val;
        node.borrow_mut().val = sum;
    }
    root
}

总结

BST的中序是很有用且很特殊的性质，很多题目基于此，熟练掌握他的中序遍历及其应用。

Bert Huang

BST inorder traverse

230. Kth Smallest Element in a BST

Question

思路

538. Convert BST to Greater Tree

Question

思路

1038. Binary Search Tree to Greater Sum Tree

Question

思路

总结