程序员面试金典-0405-合法二叉搜索树

曾经终败给现在 2022-10-19 12:39 158阅读 0赞

## 程序员面试金典-0405-合法二叉搜索树 ##

思路：1. 通过二叉搜索树中序遍历  
2. 遍历中序遍历的结果，如果是有序的话，则为合法二叉搜索树

实现一个函数，检查一棵二叉树是否为二叉搜索树。
    
    示例 1:
    输入:
        2
       / \
      1   3
    输出: true
    示例 2:
    输入:
        5
       / \
      1   4
         / \
        3   6
    输出: false
    解释: 输入为: [5,1,4,null,null,3,6]。
         根节点的值为 5 ，但是其右子节点值为 4 。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/legal-binary-search-tree-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    struct list_node{
        
        int val;
        struct list_node * next;
    };
    void inorder_traverse(struct TreeNode * root,struct list_node * head);
    
    bool isValidBST(struct TreeNode* root){
        
        bool ret = true;
        struct list_node * head = malloc(sizeof(struct list_node));
        head->val = -1;
        head->next = NULL;
        inorder_traverse(root,head);
        struct list_node * t = head->next;
        while(t!=NULL){
        
            if(t->next == NULL)
                break;
            int t1 = t->val;
            int t2 = t->next->val;
            if(t2>=t1){
        
                ret = false;
                break;
            }
            t = t->next;
        }
        return ret;
    }
    
    void inorder_traverse(struct TreeNode * root,struct list_node * head){
        
        if(root == NULL)
            return;
        inorder_traverse(root->left,head);
        int t = root->val;
        struct list_node * temp = malloc(sizeof(struct list_node));
        temp->val = t;
        temp->next = head->next;
        head->next = temp;
        inorder_traverse(root->right,head);
    }