Day20 二叉搜索树的第k大节点 + 平衡二叉树 + 调整数组

TODO:
1.重做二叉平衡树 ❗

一、剑指 Offer 54. 二叉搜索树的第k大节点(简单)

方法一 傻瓜式中序遍历

class Solution {
public:
    vector<int> item;
    void dfs(TreeNode* root){
        if(!root) return ;
        dfs(root->left);
        item.push_back(root->val);
        dfs(root->right);
    }
    int kthLargest(TreeNode* root, int k) {
        if(root == nullptr) return 0;
        dfs(root);
        int t = item.size();
        return item[t-k];
    }
};

方法二 右根左

class Solution {
public:
    int kmax;
    int t;
    void dfs(TreeNode* root){
        if(!root) return ;
        dfs(root->right);
        if(t ==0){kmax = root->val;}
        t-=1;
        dfs(root->left);
    }
    int kthLargest(TreeNode* root, int k) {
        if(root == nullptr) return 0;
        t = k-1;
        dfs(root);
        return kmax;
    }
};

方法三 简洁的写法

class Solution {
public:
   int a;
   int kthLargest(TreeNode* root, int k) {
       dfs(root, k);
       return a;
   }
   void dfs(TreeNode* root, int& k)
   {
       if(!root) return;
       dfs(root->right, k);
       k--;
       if(!k) a = root->val;
       if(k > 0) dfs(root->left, k);
   }
};

二、 剑指 Offer 55 - II. 平衡二叉树(简单)⭐

多简单的一道题啊，不会。题解

方法一 后续遍历从底到顶

class Solution {
public:
    int height(TreeNode* root){
        if(root == nullptr) return 0;
        int left = height(root->left);
        if(left == -1) return -1;
        int right = height(root->right);
        if(right == -1) return -1;
        return abs(right-left)<=1? max(left,right)+1:-1;
    }
    bool isBalanced(TreeNode* root) {
        return height(root)==-1? false:true;
    }
};

三、剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

方法一 自己瞎搞的双指针

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int n = nums.size();
        if(n==0)return {};
        int i = 0, j = n-1;
        while(i <= j){
            while(i<j&&nums[i]%2!=0){i++;}
            while(i<j&&nums[j]%2==0){j--;}
            swap(nums[i],nums[j]);
            i++;
            j--;
        }
        return nums;
    }
};