05 二叉搜索树的属性

​ 二叉查找树 / 二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树：对于每个父节点，其左子节点的值小于等于父结点的值，其右子节点的值大于等于父结点的值。因此对于一个二叉查找树，我们可以在 O(nlogn) 的时间内查找一个值是否存在：从根节点开始，若当前节点的值大于查找值则向左下走，若当前节点的值小于查找值则向右下走。同时因为二叉查找树是有序的，对其中序遍历的结果即为排好序的数组。 ​ 一个二叉查找树的实现如下：

template <class T>
class BST {
    struct Node {
        T data;
        Node* left;
        Node* right;
    };
    
    Node* root;
    
    Node* makeEmpty(Node* t) {
        if (t == NULL) return NULL;
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
        return NULL;
    }
    
    Node* insert(Node* t, T x) {
        if (t == NULL) {
            t = new Node;
            t->data = x;
            t->left = t->right = NULL;
        } else if (x < t->data) {
            t->left = insert(t->left, x);
        } else if (x > t->data) {
            t->right = insert(t->right, x);
        }
        return t;
    }
    
    Node* find(Node* t, T x) {
        if (t == NULL) return NULL;
        if (x < t->data) return find(t->left, x);
        if (x > t->data) return find(t->right, x);
        return t;
    }
    
    Node* findMin(Node* t) {
        if (t == NULL || t->left == NULL) return t;
        return findMin(t->left);
    }
    
    Node* findMax(Node* t) {
        if (t == NULL || t->right == NULL) return t;
        return findMax(t->right);
	}
    
    Node* remove(Node* t, T x) {
        ode* temp;
        if (t == NULL) return NULL;
        else if (x < t->data) t->left = remove(t->left, x);
        else if (x > t->data) t->right = remove(t->right, x);
        else if (t->left && t->right) {
            temp = findMin(t->right);
            t->data = temp->data;
            t->right = remove(t->right, t->data);
        } else {
            temp = t;
            if (t->left == NULL) t = t->right;
            else if (t->right == NULL) t = t->left;
            delete temp;
        }
        return t;
    }

public:
    BST(): root(NULL) {}
    ~BST() {
        root = makeEmpty(root);
    }
    void insert(T x) {
    	insert(root, x);
    }
    void remove(T x) {
    	remove(root, x);
    }
};  

​ 二叉搜索树的特点是节点左子树都小于节点值，节点右子树都大于节点值。所以，二叉搜索树的中序遍历序列就是一个递增序列，这一属性被广泛使用。

538 把二叉搜索树转换为累加树 (opens new window)

给出一个二叉搜索树，该树的节点值各不相同，请将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

输入一个二叉搜索树，输出一个累加树

输入：root = [3,2,4,1]
输出：[7,9,4,10]

解析：

​ 本题可以采用返序的中序遍历解决，中序遍历先遍历左节点、再遍历根节点、最后遍历右节点。

​ 而二叉搜索树的特点是节点左子树都小于节点值，节点右子树都大于节点值；累加树又是累加的是大于等于当前节点值的节点；所以只要从二叉搜索树最底层，最右侧开始遍历，就可以自下而上累加节点值。

​ 即当前节点值为其右子数最大累和加上自身节点值，而最大累和在右子树存在左子树的情况下出现在该左子数最底层最左侧节点累加值。

​ 根据累加树的节点值累加顺序：先右节点累和，然后根节点基于右节点值进行累和，最后左节点根据根节点值进行累和。所以本题采用返序中序遍历，先遍历右节点、再遍历根节点、最后遍历左节点；同时需要一个累和全局变量存储遍历当前节点时已经被遍历节点值之和。

​ 简而言之，按从大到小的顺序遍历二叉搜索树，每遍历一个节点，加上自身节点值来更新累和值，并将累和值作为其新值。

class Solution {
    // 存储遍历当前节点时已经被遍历节点值之和
    int sum = 0;
public:
    TreeNode* convertBST(TreeNode* root) {
        if(!root){
            return root;
        }
        // 先遍历右节点
        convertBST(root->right);
        // 在遍历根节点
        sum+=root->val;
        root->val = sum;
        // 最后遍历左节点
        convertBST(root->left);
        return root;
    }
};

235 二叉搜索树的最近公共祖先 (opens new window)

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先

输入一个二叉搜索树，输出一个节点表示两个指定节点的最近公共祖先

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 0, q = 3 输出: 2 解释: 节点 0 和节点 3 的最近公共祖先是 2。

解析：

​ 二叉搜索树的特点是节点左子树都小于节点值，节点右子树都大于节点值。

​ 利用此特性可以仅使用一遍遍历就可以找出最近公共祖先：

​ 从根节点开始遍历，如果 p 和 q 的值均小于当前节点的值，说明 p 和 q 应该在当前节点的左子树，将当前节点移动到它的左子节点。

​ 如果 p 和 q 的值均大于当前节点的值，说明 p 和 q 应该在当前节点的右子树，将当前节点移动到它的右子节点。

​ 如果当前节点的值不满足上述两条要求，即 p 和 q 分别位于当前节点的左右子树，那么说明当前节点就是 p 和 q 最近公共祖先。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root){
            return root;
        }
        while(true){
            if(root->val < p->val && root->val < q->val){
                root = root->right;
            }else if(root->val > p->val && root->val > q->val){
                root = root->left;
            }else{
                break;
            }
        }
        return root;
    }
};

236 二叉树的最近公共祖先 (opens new window)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

输入一个二叉树，输出一个节点表示两个指定节点的最近公共祖先

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 6, q = 7 输出：5 解释：节点 6 和节点 7 的最近公共祖先是节点 5

解析：

​ 二叉树不具备二叉搜索树的特点，所以要递归遍历查找。但是思想是一样的，判断是 p 和 q 是否分别位于当前节点的左右子树。

​ 采用深度优先搜索的遍历方法，递归遍历当前节点的左右子树：

​ 递归终止条件：当前节点为叶子节点或者刚好是 p 或者 q 节点。

​ 采用自上而下的递归遍历左右子树，返会结果时自下而上返回保证了返回的公共祖先是最近的。

​ 如果左右子树递归遍历返回结果都为真，那么说明 p 和 q 位于当前节点的左右子树，直接返回当前节点。如果左子树递归遍历结果为假，则说明 p 和 q 位于当前节点的右子树，返回右节点；如果右子树递归遍历结果为假，则说明 p 和 q 位于当前节点的左子树，返回左节点；如果左右子树递归遍历返回结果都为假，那么说明 p 和 q 不在以当前节点为根节点的子树中。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q){
            return root;
        }
        auto left = lowestCommonAncestor(root->left,p,q);
        auto right = lowestCommonAncestor(root->right,p,q);
        if(left && right){
            return root;
        }else if(!left){
            return right;
        }else if(!right){
            return left;
        }else{
            return nullptr;
        }
    }
};

530 二叉搜索树的最小绝对差 (opens new window)

给定一棵所有节点为非负值的二叉搜索树，请计算树中任意两节点的差的绝对值的最小值。

输入一个二叉搜索树，输出一个整数表示树中任意两节点的差的绝对值的最小值

输入：[1,null,3,null,null,2]

输出：1

解释：最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

解析：

​ 二叉搜索树的特点是节点左子树都小于节点值，节点右子树都大于节点值。那么使用二叉搜索树的中序遍历序列就是一个递增序列，利用此特点可以快速解决本题。

​ 计算任意两节点的差的绝对值的最小值，有两种思路，一种就是将二叉搜索树的中序遍历序列存储到一个数组中，然后遍历该数组计算最小差。另一种思路就是在中序遍历过程中记录前一个节点值，在遍历过程中计算两节点的差的绝对值的最小值。

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        if(!root){
            return 0;
        }
        vector<int> inorder;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        while(cur || !s.empty()){
            if(cur){
                s.push(cur);
                cur = cur->left;
            }else{
                cur = s.top();
                s.pop();
                inorder.push_back(cur->val);
                cur = cur->right;
            }
        }
        int ans = INT_MAX;
        for(int i=1;i<inorder.size();++i){
            ans = min(ans,inorder[i]-inorder[i-1]);
        }
        return ans;
    }
    
    // 一遍遍历方式：使用pre记录前一个节点值
    int getMinimumDifference(TreeNode* root) {
        if(!root){
            return 0;
        }
        int pre = -1, ans = INT_MAX;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        while(cur || !s.empty()){
            if(cur){
                s.push(cur);
                cur = cur->left;
            }else{
                cur = s.top();
                s.pop();
                if(pre==-1){
                    pre = cur->val;
                }else{
                    ans = min(ans,cur->val-pre);
                    pre = cur->val;
                }
                cur = cur->right;
            }
        }
        return ans;
    }
};

897 递增顺序搜索树 (opens new window)

给定一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

输入一个二叉搜索树，输出一个只有右节点的递增顺序搜索树

输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9] 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

解析：

​ 本题和530 二叉搜索树的最小绝对差 (opens new window)一样也可以从二叉搜索树的中序遍历是递增序列的思路解题。先设置一个空头节点，然后使用尾插法将遍历的每一个节点插入到上一节点的右节点。在中序遍历过程中将当前节点插入到上一节点的右节点，直到遍历完成。

​ 需要特别注意的是在插入节点的过程中要将当前节点的左节点置为空，因为二叉搜索树中左节点都小于当前节点，所以他们已经被插入到结果树中。如果不将左节点置为空，可能导致出现环路。

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        if(!root){
            return root;
        }
        // 创建空头节点
        TreeNode* ans = new TreeNode();
        TreeNode* tail = ans;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        while(cur || !s.empty()){
            if(cur){
                s.push(cur);
                cur = cur->left;
            }else{
                cur = s.top();
                s.pop();
                // 将当前节点作为前一节点的右节点
                tail->right = cur;
                tail = cur;
                // 将当前节点左节点置为空，避免环路
                cur->left = nullptr;
                cur = cur->right;
            }
        }
        return ans->right;
    }
};

653. 两数之和 IV - 输入 BST (opens new window)

给定一个二叉搜索树和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

输入一个二叉搜索树和目标值 k，输出一个布尔值表示是否存在两个元素之和为目标值k

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true

解析：

​ 看到两数之和很容易想到使用哈希表，那么一种最为简单的思路就是遍历二叉搜索树并将所有元素存入哈希表中。然后，遍历哈希表寻找两数之和。

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> hash;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        while(cur || !s.empty()){
            if(cur){
                s.push(cur);
                cur = cur->left;
            }else{
                cur = s.top();
                s.pop();
                hash.insert(cur->val);
                cur = cur->right;
            }
        }
        
        for(const auto elem: hash){
            if(hash.find(k-elem) != hash.end() && k-elem != elem){
                return true;
            }
        }
        return false;
    }
};