英雄算法6月20号

class Solution {
public:
    TreeNode* dfs(TreeNode* & curNode, int& val){
        if(curNode == NULL){//边界条件，如果为NULL，直接返回NULL
            return NULL;
        }else if(curNode->val == val){//如果相等，表示找到。返回当前节点
            return curNode;
        }
        return dfs(curNode->val>val?curNode->left:curNode->right,val);//因为二叉搜索树的性质，如果当前的值大，为了找到val，需要让curNode->val变小，所以需要向左遍历；反之亦然
    }
    TreeNode* searchBST(TreeNode* root, int val) {
        return dfs(root,val);
    }
};

思路

今天的题目水水的。

dfs的目的是返回节点地址。前一个节点返回的是后一个节点返回的地址。

因为是二叉搜索树，所以左节点小于右节点，因此，只要curNode->val>val,需要减小当前节点的值，才能匹配val。所以，我们需要递归左树；反之，递归右树。

//由于二叉搜索树的特性，以第二种中序遍历的方式，得到的结果恰好是递减的，所以选取前k个即可
class Solution {
    vector ans;
    void dfs(TreeNode* curNode, int& num, int k){
        if(curNode == NULL){//边界条件，返回
            return ;
        }
        if(k == num){//如果前前k个选择完毕，终止递归
            return ;
        }
        dfs(curNode->right,num,k);//向右递归
        ans.emplace_back(curNode->val);//二叉搜索树的特性，以及中序遍历的方式，决定了此时插入的元素一定是小于前一个插入的元素，插入新value
        ++num;//得到的元素++
        dfs(curNode->left,num,k);//左递归
    }
public:
    int kthLargest(TreeNode* root, int k) {
        int num = 0;
        dfs(root,num,k);
        return ans[k-1];
    }
};

思路

中序遍历完美契合二叉搜索树节点的顺序排序，只不过需要先遍历右树，打印，在遍历左树，才能实现递减。

class Solution {
public:
    TreeNode* dfs(TreeNode* & curNode, int& val){
        if(curNode == NULL){//此时节点为NULL,表示现在应该要返回新节点给父节点。这个为NULL的位置，就是要插入的位置
            TreeNode* tmp =  new TreeNode;
            tmp->val = val; tmp->left = NULL; tmp->right = NULL;
            return tmp;
        }
        if(curNode->val > val){//需要在左边寻找插入新节点的位置
            curNode->left = dfs(curNode->left,val);//把节点接上。（接上节点存在两种情况：1.已经有节点了，不需要解新节点。 2.->left==NULL,需要接上新节点。如果是前者，需要返回子节点本身，后者就是一开始的边界处理）
        }else{//需要在右边
            curNode->right = dfs(curNode->right,val);
        }
        return curNode;//不需要新建节点，因为一开始父节点指向的就是自己，所以返回自己，以免更改正确的逻辑关系
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        return dfs(root,val);
    }
};

思路

dfs搜索所有节点，并且连接新生成的节点。

• 如果当前节点为NULL，说明该位置就是新节点的位置。所以生成新节点，返回，让父节点连接。
• 如果当前节点不为NULL，但是节点的val大了，说明需要遍历左树，在左边找到一个父节点，为他接上新节点。
• 反之，遍历右树，找到一个父节点，为他接上新节点。
• 如果父节点已连接过子节点，那么子节点返回自己即可

//思路类似上题。借助中序遍历，判断节点值的大小即可
//此处以      递减顺序    为例子
class Solution {
    long int pre = 2147483657;
    bool flag = true;
    void dfs(TreeNode* & curNode){
        if(curNode == NULL) return ;//边界条件
        if(!flag) return ;//如果已经存在前一个节点<=后一个节点，flag = false。终止递归
        dfs(curNode->right);//递归遍历右树
        if(curNode->val >= pre) flag = false;//如果当前节点小于前一个节点，返回false
        pre = curNode->val;//更新上一个节点，在这之后的节点必须小于curNode->val,否则就不是二叉搜索树
        dfs(curNode->left);
    }
public:
    bool isValidBST(TreeNode* root) {
        dfs(root);
        return flag;
    }
};

中序遍历