Leetcode 刷题笔记-Leetcode 101 第14章树

树

树的递归

Leetcode 104

给定一个二叉树，找出其最大深度。

class Solution {
public:
    static int DFS(TreeNode* &root,int sum){
        if(root == nullptr){
            return sum;
        }
        return max(DFS(root->left,sum+1),DFS(root->right,sum+1));
    }
    int maxDepth(TreeNode* root) {
        return DFS(root,0);
    }
};

分析：递归计算最大高度即可

错误：开始递归写的有问题，变成引用传参了，后面改对后调通。

Leetcode 110

给定一个二叉树，判断它是否是高度平衡的二叉树。

class Solution {
public:
    static int DFS(TreeNode* &root){
        if(root == nullptr){
            return 0;
        }
        int left = DFS(root->left);
        int right = DFS(root->right);
        if(left == -1 || right == -1 || abs(left - right) > 1){
            return -1;
        }
        return max(left,right)+1;
    }
    bool isBalanced(TreeNode* root) {
        return DFS(root) != -1;
    }
};

分析：解法类似于求树的最大深度，但有两个不同的地方：一是我们需要先处理子树的深度再进行比较，二是如果我们在处理子树时发现其已经不平衡了，则可以返回一个-1，使得所有其长辈节点可以避免多余的判断

错误：思路不对，看了解析

Leetcode 543

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

class Solution {
public:
    static int DFS(TreeNode* &root,int &maxsum){
        if(root == nullptr){
            return 0;
        }
        int left = DFS(root->left,maxsum);
        int right = DFS(root->right,maxsum);
        maxsum = max(maxsum,left+right+1);
        return max(left,right)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int maxsum = 0;
        int a = DFS(root,maxsum);
        return maxsum-1;
    }
};

分析：还是递归，要留两个变量进行记录

错误：没看解析调通，但是自己想的挺艰难的。

Leetcode 437

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

class Solution {
public:
    static long long DFS(TreeNode* &root, long long sum){
        if(root == nullptr){
            return 0;
        }
        long long count;
        if(root->val == sum){
            count = 1;
        }
        else{
            count = 0;
        }
        return count + DFS(root->left,sum-root->val) + DFS(root->right,sum-root->val);
    }
    int pathSum(TreeNode* root, int targetSum) {
        if(root == nullptr){
            return 0;
        }
        return DFS(root,targetSum)+pathSum(root->left,targetSum)+pathSum(root->right,targetSum);
    }
};

分析：递归每个节点时，需要分情况考虑：（1）如果选取该节点加入路径，则之后必须继续加入连续节点，或停止加入节点（2）如果不选取该节点加入路径，则对其左右节点进行重新进行考虑。因此一个方便的方法是我们创建一个辅函数，专门用来计算连续加入节点的路径。

错误：两层的递归有点做不了

Leetcode 101

给你一个二叉树的根节点 root ，检查它是否轴对称。

class Solution {
public:
    static bool DFS(TreeNode* &left,TreeNode* &right){
        if(left == nullptr && right != nullptr){
            return false;
        }
        if(left != nullptr && right == nullptr){
            return false;
        }
        if(left == nullptr && right == nullptr){
            return true;
        }
        if(left->val != right->val){
            return false;
        }
        return DFS(left->left,right->right) && DFS(left->right,right->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        return DFS(root->left,root->right);
    }
};

分析：判断一个树是否对称等价于判断左右子树是否对称。笔者一般习惯将判断两个子树是否相等或对称类型的题的解法叫做“四步法”：（1）如果两个子树都为空指针，则它们相等或对称（2）如果两个子树只有一个为空指针，则它们不相等或不对称（3）如果两个子树根节点的值不相等，则它们不相等或不对称（4）根据相等或对称要求，进行递归处理。

错误：不明白

Leetcode 1110

给出二叉树的根节点 root，树上每个节点都有一个不同的值。如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。返回森林中的每棵树。你可以按任意顺序组织答案。

class Solution {
public:
    void DFS(TreeNode* &root, vector<int>& to_delete,vector<TreeNode*>& result){
        if(root == nullptr){
            return;
        }
        DFS(root->left,to_delete,result);
        DFS(root->right,to_delete,result);
        auto it = find(to_delete.begin(),to_delete.end(),root->val);
        if(it != to_delete.end()){
            if(root->left != nullptr){
                result.push_back(root->left);
            }
            if(root->right != nullptr){
                result.push_back(root->right);
            }
            root->left = nullptr;
            root->right = nullptr;
            root = nullptr;
        }
        return;
    }
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        vector<TreeNode*> result;
        DFS(root,to_delete,result);
        if(root != nullptr){
            result.push_back(root);
        }
        return result;
    }
};

分析：遍历，然后置为空指针就好

错误：开始的判断条件不太够，后来自己调通。

层次遍历

Leetcode 637

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10<sup>-5</sup> 以内的答案可以被接受。

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int num = 0;
            double sum = 0.0;
            int nowsize = q.size();
            while(nowsize--){
                TreeNode* t = q.front();
                q.pop();
                num += 1;
                sum += t->val;
                if(t->left != nullptr){
                    q.push(t->left);
                }
                if(t->right != nullptr){
                    q.push(t->right);
                }
            }
            result.push_back(sum/num);
        }
        return result;
    }
};

分析：层序遍历即可

一遍AC

前中后序遍历

Leetcode 105

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的 先序遍历 ， inorder 是同一棵树的 中序遍历 ，请构造二叉树并返回其根节点。

class Solution {
private:
    unordered_map<int, int> index;
public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
  
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = index[preorder[preorder_root]];
  
        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        // 构造哈希映射，帮助我们快速定位根节点
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

分析：很老的题，好好判断，数据结构设计对即可

错误：太久远了忘记怎么判断了

Leetcode 144

给你二叉树的根节点 root ，返回它节点值的前序遍历。

class Solution {
public:
    static void dfs(TreeNode* &root,vector<int> &result){
        if(root == nullptr){
            return;
        }
        result.push_back(root->val);
        dfs(root->left,result);
        dfs(root->right,result);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root,result);
        return result;
    }
};

分析：递归遍历即可

一遍AC

二叉查找树

Leetcode 99

给你二叉搜索树的根节点 root ，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树。

class Solution {
public:
    void inorder(TreeNode* root, TreeNode*& mistake1, TreeNode*& mistake2, TreeNode*& prev) {
        if (!root) {
            return;
        }
        if (root->left) {
            inorder(root->left, mistake1, mistake2, prev);
        }
        if (prev && root->val < prev->val) {
            if (!mistake1) {
                mistake1 = prev;
                mistake2 = root;
            }
            else {
                mistake2 = root;
            }
            cout << mistake1->val;
            cout << mistake2->val;
        }
        prev = root;
        if (root->right) {
            inorder(root->right, mistake1, mistake2, prev);
        }
    }
    void recoverTree(TreeNode* root) {
        TreeNode *mistake1 = nullptr, *mistake2 = nullptr, *prev = nullptr;
        inorder(root, mistake1, mistake2, prev);
        if (mistake1 && mistake2) {
            int temp = mistake1->val;
            mistake1->val = mistake2->val;
            mistake2->val = temp;
        }
    }
};

分析：我们可以使用中序遍历这个二叉查找树，同时设置一个prev 指针，记录当前节点中序遍历时的前节点。如果当前节点大于prev 节点的值，说明需要调整次序。有一个技巧是如果遍历整个序列过程中只出现了一次次序错误，说明就是这两个相邻节点需要被交换；如果出现了两次次序错误，那就需要交换这两个节点。

错误：没有思路

Leetcode 669

给你二叉搜索树的根节点 root ，同时给定最小边界 low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在 [low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == nullptr){
            return root;
        }
        if(root->val > high){
            return trimBST(root->left,low,high);
        }
        if(root->val < low){
            return trimBST(root->right,low,high);
        }
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

分析：利用二叉查找树的大小关系递归进行树的处理。

错误：看了解析

字典树

Leetcode 208

尝试建立一个字典树，支持快速插入单词、查找单词、查找单词前缀的功能。

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }
public:
    Trie() : children(26), isEnd(false) {}
    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};

分析：字典树的典型实现方法

错误：没做过，尝试理解

练习

Leetcode 226

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr){
            return nullptr;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

分析：递归反转即可

错误：翻转值是不对的，需要反转结点

Leetcode 617

给你两棵二叉树： root1 和 root2 。想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。返回合并后的二叉树。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) {
            return t2;
        }
        if (t2 == nullptr) {
            return t1;
        }
        auto merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left, t2->left);
        merged->right = mergeTrees(t1->right, t2->right);
        return merged;
    }
};

分析：递归处理即可

错误：自己尝试的方法有问题，不太明白错在哪

Leetcode 572

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

class Solution {
public:
    static bool check(TreeNode* root, TreeNode* subRoot){
        if(root == nullptr && subRoot == nullptr){
            return true;
        }
        if(root == nullptr && subRoot != nullptr){
            return false;
        }
        if(root != nullptr && subRoot == nullptr){
            return false;
        }
        if(root->val != subRoot->val){
            return false;
        }
        return check(root->left,subRoot->left) && check(root->right,subRoot->right);
    }
    static bool DFS(TreeNode* root, TreeNode* subRoot){
        if(root == nullptr){
            return false;
        }
        return check(root,subRoot) || DFS(root->left,subRoot) || DFS(root->right,subRoot);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        bool judge = DFS(root,subRoot);
        return judge;
    }
};

分析：递归判断即可

错误：自己写了前半部分，看了一眼后写了后半部分

Leetcode 404

给定二叉树的根节点 root ，返回所有左叶子之和。

class Solution {
public:
    bool isLeafNode(TreeNode* node) {
        return !node->left && !node->right;
    }

    int dfs(TreeNode* node) {
        int ans = 0;
        if (node->left) {
            ans += isLeafNode(node->left) ? node->left->val : dfs(node->left);
        }
        if (node->right && !isLeafNode(node->right)) {
            ans += dfs(node->right);
        }
        return ans;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        return dfs(root);
    }
};

分析：递归判断结点

错误：没有思路

Leetcode 513

给定一个二叉树的 根节点 root，请找出该二叉树的最底层最左边节点的值。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int result = root->val;
        while(!q.empty()){
            int tempsize = q.size();
            int sign = 0;
            while(tempsize--){
                TreeNode* t = q.front();
                q.pop();
                if(sign == 0){
                    result = t->val;
                    sign = 1;
                }
                if(t->left != nullptr){
                    q.push(t->left);
                }
                if(t->right != nullptr){
                    q.push(t->right);
                }
            }
        }
        return result;
    }
};

分析：广度优先遍历即可

一遍AC

Leetcode 538

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

class Solution {
public:
    void DFS(TreeNode* root,int &sum){
        if(root == nullptr){
            return;
        }
        DFS(root->right,sum);
        root->val = root->val + sum;
        sum = root->val;
        DFS(root->left,sum);
        return;
    }
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        DFS(root,sum);
        return root;
    }
};

分析：反向的中序遍历

错误：开始顺序弄反，后面修正了

Leetcode 235

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

class Solution {
public:
    vector<TreeNode*> getPath(TreeNode* root, TreeNode* target) {
        vector<TreeNode*> path;
        TreeNode* node = root;
        while (node != target) {
            path.push_back(node);
            if (target->val < node->val) {
                node = node->left;
            }
            else {
                node = node->right;
            }
        }
        path.push_back(node);
        return path;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> path_p = getPath(root, p);
        vector<TreeNode*> path_q = getPath(root, q);
        TreeNode* ancestor;
        for (int i = 0; i < path_p.size() && i < path_q.size(); ++i) {
            if (path_p[i] == path_q[i]) {
                ancestor = path_p[i];
            }
            else {
                break;
            }
        }
        return ancestor;
    }
};

分析：从根节点开始遍历；如果当前节点就是p，那么成功地找到了节点；如果当前节点的值大于p的值，说明p应该在当前节点的左子树，因此将当前节点移动到它的左子节点；如果当前节点的值小于p的值，说明p应该在当前节点的右子树，因此将当前节点移动到它的右子节点。对于节点q同理。在寻找节点的过程中，我们可以顺便记录经过的节点，这样就得到了从根节点到被寻找节点的路径。

错误：没有思路

Leetcode 530

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

class Solution {
public:
    void DFS(TreeNode* &root,vector<int>& result){
        if(root == nullptr){
            return;
        }
        DFS(root->left,result);
        result.push_back(root->val);
        DFS(root->right,result);
    }
    int getMinimumDifference(TreeNode* root) {
        vector<int> result;
        DFS(root,result);
        int minval = 100000;
        for(int i=0;i<result.size()-1;++i){
            if(result[i+1]-result[i] < minval){
                minval = result[i+1]-result[i];
            }
        }
        return minval;
    }
};

分析：中序遍历存在数组内部，然后遍历判断即可

一遍AC

Leetcode 889

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

class Solution {
    int preIdx = 0, postIdx = 0;
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        TreeNode *node = new TreeNode(preorder[preIdx++]);
        if(node->val != postorder[postIdx]){
            node->left = constructFromPrePost(preorder, postorder);
        }

        if(node->val != postorder[postIdx]){
            node->right = constructFromPrePost(preorder, postorder);
        }
        postIdx++;
        return node;
    }
};

分析：利用前序遍历来构建Tree，然后通过后续遍历来检验当前树是否构建完毕 。

错误：思路不对

Leetcode 106

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

class Solution {
public:
    TreeNode* DFS(vector<int>& inorder, int inleft,int inright,vector<int>& postorder,int postleft,int postright){
        if(inleft > inright){
            return nullptr;
        }
        TreeNode* root = new TreeNode(postorder[postright]);
        int k;
        for(k=inleft;k<=inright;++k){
            if(inorder[k] == postorder[postright]){
                break;
            }
        }
        int rightsize = inright - k;
        root->left = DFS(inorder,inleft,k-1,postorder,postleft,postright-rightsize-1);
        root->right = DFS(inorder,k+1,inright,postorder,postright-rightsize,postright-1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        TreeNode* root = DFS(inorder,0,n-1,postorder,0,n-1);
        return root;
    }
};

分析：与前面的题目相同

一遍AC

Leetcode 94

给定一个二叉树的根节点 root ，返回它的中序遍历。

class Solution {
public:
    static void dfs(TreeNode* &root,vector<int> &result){
        if(root == nullptr){
            return;
        }
        dfs(root->left,result);
        result.push_back(root->val);
        dfs(root->right,result);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root,result);
        return result;
    }
};

分析：普通递归

一遍AC

Leetcode 145

给你一棵二叉树的根节点 root ，返回其节点值的后序遍历。

class Solution {
public:
    static void dfs(TreeNode* &root,vector<int> &result){
        if(root == nullptr){
            return;
        }
        dfs(root->left,result);
        dfs(root->right,result);
        result.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root,result);
        return result;
    }
};

分析：普通递归

一遍AC

Leetcode 236

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
            ans = root;
        } 
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

分析：不太明白

错误：不太明白

Leetcode 109

给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。

class Solution {
public:
    ListNode* getMedian(ListNode* left, ListNode* right) {
        ListNode* fast = left;
        ListNode* slow = left;
        while (fast != right && fast->next != right) {
            fast = fast->next;
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }

    TreeNode* buildTree(ListNode* left, ListNode* right) {
        if (left == right) {
            return nullptr;
        }
        ListNode* mid = getMedian(left, right);
        TreeNode* root = new TreeNode(mid->val);
        root->left = buildTree(left, mid);
        root->right = buildTree(mid->next, right);
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        return buildTree(head, nullptr);
    }
};

分析：每一次找中位数，然后递归构造两边就可以了

错误：以为要调整平衡，没有思路

Leetcode 897

给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

class Solution {
public:
    void inorder(TreeNode *node, vector<int> &res) {
        if (node == nullptr) {
            return;
        }
        inorder(node->left, res);
        res.push_back(node->val);
        inorder(node->right, res);
    }
    TreeNode* increasingBST(TreeNode* root) {
        vector<int> res;
        inorder(root, res);

        TreeNode *dummyNode = new TreeNode(-1);
        TreeNode *currNode = dummyNode;
        for (int value : res) {
            currNode->right = new TreeNode(value);
            currNode = currNode->right;
        }
        return dummyNode->right;
    }
};

分析：遍历建树就可以，注意不要在函数中建树，原因没明白

错误：在函数中建树不行

Leetcode 653

给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。

class Solution {
public:
    void DFS(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }
        DFS(root->left,result);
        result.push_back(root->val);
        DFS(root->right,result);
        return;
    }
    bool findTarget(TreeNode* root, int k) {
        vector<int> result;
        DFS(root,result);
        int left = 0;
        int right = result.size()-1;
        while(left < right){
            if(result[left] + result[right] == k){
                return true;
            }
            else if(result[left] + result[right] < k){
                ++left;
            }
            else{
                --right;
            }
        }
        return false;
    }   
};

分析：读出来二分就可以了

一遍AC

Leetcode 450

给定一个二叉搜索树的根节点root和一个值key，删除二叉搜索树中的key对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) {
            return nullptr;
        }
        if (root->val > key) {
            root->left = deleteNode(root->left, key);
            return root;
        }
        if (root->val < key) {
            root->right = deleteNode(root->right, key);
            return root;
        }
        if (root->val == key) {
            if (!root->left && !root->right) {
                return nullptr;
            }
            if (!root->right) {
                return root->left;
            }
            if (!root->left) {
                return root->right;
            }
            TreeNode *successor = root->right;
            while (successor->left) {
                successor = successor->left;
            }
            root->right = deleteNode(root->right, successor->val);
            successor->right = root->right;
            successor->left = root->left;
            return successor;
        }
        return root;
    }
};

分析：解析

错误：不明白应该怎么调整

总结

看起来树的题目并没有特别复杂的。主要的难度在于递归的思路，想明白后就简单了。另外就是各种边界条件的判断，也要多想多练。

Study

#Algorithm #C++ #Leetcode

Leetcode 刷题笔记-Leetcode 101 第14章树

https://zhangzhao219.github.io/2022/09/16/Leetcode/Leetcode-101/Leetcode-101-14/

作者

Zhang Zhao

发布于

2022年9月16日

许可协议

研究生课程：现代信息检索-第7讲基于语言建模的IR模型上一篇

研究生课程：机器学习-第3章线性分类下一篇

Leetcode 刷题笔记-Leetcode 101 第14章 树

树

树的递归

Leetcode 104

Leetcode 110

Leetcode 543

Leetcode 437

Leetcode 101

Leetcode 1110

层次遍历

Leetcode 637

前中后序遍历

Leetcode 105

Leetcode 144

二叉查找树

Leetcode 99

Leetcode 669

字典树

Leetcode 208

练习

Leetcode 226

Leetcode 617

Leetcode 572

Leetcode 404

Leetcode 513

Leetcode 538

Leetcode 235

Leetcode 530

Leetcode 889

Leetcode 106

Leetcode 94

Leetcode 145

Leetcode 236

Leetcode 109

Leetcode 897

Leetcode 653

Leetcode 450

总结

Leetcode 刷题笔记-Leetcode 101 第14章树