二叉搜索树的命运和中阶遍历

二叉搜索树的一个重要特征是树中任何节点的左子树中所有节点的值小于该节点的值，而右子树中所有节点的值均为小于节点Big. 按顺序遍历二叉搜索树会产生一个升序的排序序列.

要检查树是否为二叉搜索树二叉排序树 遍历，可以使用中间顺序遍历二叉排序树 遍历，也可以使用中间顺序遍历根据递增的排序顺序生成两权重搜索树. 通常有可能使用中阶遍历来解决二叉搜索树的问题，以获得最佳时间复杂度（不考虑递归时间损失）. 为了解决这两个问题，有必要在遍历过程中记录与当前位置有关的信息.

1. 检查树是否是二叉搜索树.

98. 验证二进制搜索树

使用有序遍历进行求解.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if(!root) return true;
        return (isValidBST(root->left) && isValidVal(root->val) && isValidBST(root->right)); //中序遍历
    }
private:
    bool isValidVal(int val) {
        if(bFirstNode) {
            bFirstNode = false;
            prevNodeVal = val;
            return true;
        }
        if(prevNodeVal >= val) return false;
        prevNodeVal = val;
        return true;
    }
    bool bFirstNode = true;
    int prevNodeVal = 0; //记录前一个结点的值
};

2. 根据增加的顺序生成一个二重搜索树.

109. 将排序列表转换为二进制搜索树

使用有序遍历进行求解.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-212670-1.html