leetcode 109 将排序链表转换成平衡二叉搜索树

没得思路，猜一下，将排序链表平分，前面的作为左子树，后面的作为右子树，中间的作为根节点。

找链表中间的节点的思路: 前两篇提到过,快慢指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * 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:
    TreeNode* helper(ListNode* head,ListNode* end){
        if(head==end) return NULL;
        ListNode* slow=head,*fast=head;
        while(fast!=end&&fast->next!=end){
            slow=slow->next;
            fast=fast->next->next;
        }
        
        TreeNode* root=new TreeNode(slow->val);
        root->left=helper(head,slow);
        root->right=helper(slow->next,end);
        return root;
    }
    
    
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return NULL;
        return helper(head,NULL);
    }
};

最快的代码是利用数字表示位置，逐步逼近链表中点的，不过优化的效果不是很明显(小声比比),不优化了

怎样检验树是平衡的

顺便复习一下子,树是平衡的，也就是每个节点的左子树和右子树的高度相差不超过1，所以遍历所有节点，求左子树高度和右子树高度，判断高度差就可以啦：

int height(TreeNode* root){
    if(!root) return 0;
    int left=height(root->left);
    int right=height(root->right);
    return left>right:left+1:right+1;
}


bool is_balance_tree(TreeNode* root){
    if(root==NULL) return true;
    int left=height(root->left);
    int right=height(root->right);
    int diff=left>right?left-right:right-left;
    if(diff>1) return false;

    return is_balance_tree(root->left)&&is_balance_tree(root->right);
}

但是上面的方法固然可以运行，但是效率很低，因为每当遍历一个节点时，我们就要遍历所有的子节点一次求高度，重复了大量的运算。 我们可以想办法把求高度的过程放在判断平衡树的过程中。

所以顺路干掉了 leetcode 110

/**
 * 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 is_balance(TreeNode* root,int &height){
        if(root==NULL){
            height=0;
            return true;
        }
        int height1=0,height2=0;
        bool left=is_balance(root->left,height1);
        bool right=is_balance(root->right,height2);
        height=height1>height2?height1+1:height2+1;
        int diff=height1>height2?height1-height2:height2-height1;
        if(diff>1) return false;
        
        return left&&right;
    }
    
    
    
    bool isBalanced(TreeNode* root) {
        int height=0;
        return is_balance(root,height);
    }
};

饭后甜点将排序数组转换成二叉搜索树

/**
 * 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:
    
    TreeNode* helper(vector<int>&nums,int start,int end){
        if(start==end){return NULL;}
        int middle=(start+end)/2;
        TreeNode* root=new TreeNode(nums[middle]);
        root->left=helper(nums,start,middle);
        root->right=helper(nums,middle+1,end);
        return root;
    }
    
    
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int size=nums.size();
        if(nums.size()==0) return NULL;
        return helper(nums,0,size);
        
        
    }
};

leetcode 109 将排序链表转换成平衡二叉搜索树

怎样检验树是平衡的

饭后甜点 将排序数组转换成二叉搜索树

饭后甜点将排序数组转换成二叉搜索树