CS杂物

二叉树中等题

By lbyxiaolizi 156 Views 30 MIN READ 0 Comments

98. 验证二叉搜索树

本题要求验证二叉搜索树是否有效，也就是递归比较验证左子树的节点都严格小于当前节点，右子树的节点都严格大于右子树。

class Solution {
public:
    bool check(TreeNode* root,long long lower,long long upper){
        if(root==nullptr) return true;

        if(root->val<=lower || root->val >=upper) return false;
        return check(root->left,lower,root->val) && check(root->right,root->val,upper);
    }
    bool isValidBST(TreeNode* root) {
        return check(root,LLONG_MIN,LLONG_MAX);
    }
};

230. 二叉搜索树中第 K 小的元素

本题要找第 k 小的元素，结合前面前面中序遍历得到的列表直接是一个升序列表，所以最简单的思路直接是中序遍历然后取 k-1 下标即可

class Solution {
public:
    void inorder(TreeNode* root,vector<int>& res){
        if(!root) return;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> res;
        inorder(root,res);
        return res[k-1];
    }
};

在上面的方法中我们存储了整个遍历出来的列表，但是实际上只用得到一个，所以我们可以在不需要的时候直接忽略掉，只存储需要的第 k 个元素。

class Solution {
public:
    int value=0;
    int i=0;
    void inorder(TreeNode* root,int k){
        if(!root) return;
        inorder(root->left,k);
        i++;
        if(i==k){
            value=root->val;
        }
        inorder(root->right,k);
    }
    int kthSmallest(TreeNode* root, int k) {
        inorder(root,k);
        return value;
    }
};

用迭代写法可以适当优化空间

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        TreeNode* curr=root;
        while(!st.empty() || curr!=nullptr){
            while(curr!=nullptr){
                st.push(curr);
                curr=curr->left;
            }
            curr=st.top();
            st.pop();
            k--;
            if(k==0){
                return curr->val;
            }
            curr=curr->right;
        }
        return -1;
    }
};

199. 二叉树的右视图

题目让去二叉树从右侧看到的节点值的数组……完全不说任何，翻译一下：每层最右节点组成的升序列表。

走层序遍历把每层最后一个 pop 出的值加进列表即可。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                TreeNode* node=q.front();
                q.pop();
                if(i==size-1){
                    res.push_back(node->val);
                }
                if(node->left){
                    q.push(node->left);
                }
                if(node->right){
                    q.push(node->right);
                }
            }
        }
        return res;
    }
};

114. 二叉树展开为链表

本题要求把二叉树按照前序遍历展开成一个链表，且要求空间复杂度为O(1)，思路比较自然，只需要注意指针连、断的顺序和有没有影响其他节点就行

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* curr=root;
        while(curr){
            TreeNode* back=curr;
            if(curr->left != nullptr){
                TreeNode* pre=curr->left;
                while(pre->right != nullptr){
                    pre=pre->right;
                }
                pre->right=curr->right;
                curr->right=curr->left;
                curr->left=nullptr;
            }
            curr=curr->right;
        }
    }
};

105. 从前序与中序遍历序列构造二叉树

本题给定一个二叉树的前序遍历和中序遍历要求重建这个二叉树……

这是一个在纸上很好推的问题，但是换成代码就有点让人发懵了。

经过一番分析后会发现规律：preorder 的第一个一定的根，inorder 中根左边的一坨是左子树，右边的一坨是右子树，于是递归。

也即 preorder 负责找根，inorder 负责切左右子树。

按照这个思路进行模拟，可以写出一个笨笨的代码

class Solution {
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder){
        if(preorder.empty()){
            return nullptr;
        }
        int root_val=preorder[0];
        TreeNode* root=new TreeNode(root_val);
        int mid=0;
        while(inorder[mid]!=root_val){
            mid++;
        }
        vector<int> left_pre(preorder.begin()+1,preorder.begin()+1+mid);
        vector<int> left_in(inorder.begin(),inorder.begin()+mid);
        vector<int> right_pre(preorder.begin()+1+mid,preorder.end());
        vector<int> right_in(inorder.begin()+mid+1,inorder.end());
        root->left=build(left_pre,left_in);
        root->right=build(right_pre,right_in);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return(build(preorder,inorder));
    }
};

优化一下，完全不是给人看的了，绕的要死，但是把空间和时间都压到了O(n)

这题真 Medium 吗

class Solution {
public:
    unordered_map<int,int> pos;
    TreeNode* build(vector<int>& preorder,int left_pre,int right_pre,int left_in,int right_in){
        if(left_pre>right_pre){
            return nullptr;
        }

        int root_val=preorder[left_pre];
        TreeNode* root=new TreeNode(root_val);

        int root_index=pos[root_val];
        int left_size=root_index-left_in;
        root->left=build(preorder,left_pre+1,left_pre+left_size,left_in,root_index-1);
        root->right=build(preorder,left_pre+left_size+1,right_pre,root_index+1,right_in);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i=0;i<inorder.size();i++){
            pos[inorder[i]]=i;
        }
        return build(preorder,0,preorder.size()-1,0,inorder.size()-1);
    }
};

437. 路径总和 III

本题要求计算二叉树里节点值之和等于给定数字的路径数目，最暴力的解法就是先写从根节点出发的节点值之和等于给定数字的路径条目，在把每个节点都当做根节点跑一遍加起来即可.

class Solution {
public:
    long long countFrom(TreeNode* root, long long targetSum){
        if(!root) return 0;
        long long ans=0;
        if(root->val==targetSum) ans++;
        ans+=countFrom(root->left,targetSum-root->val);
        ans+=countFrom(root->right,targetSum-root->val); 
        return ans;
    }
    int pathSum(TreeNode* root, int targetSum) {
        if(!root) return 0;
        int sum=0;
        sum+=countFrom(root,targetSum);
        sum+=pathSum(root->left,targetSum);
        sum+=pathSum(root->right,targetSum);
        return sum;
    }
};

当然，本题还能继续优化，仔细思考后会发现路径之和刚好是一种前缀和，所以可以利用前缀和的特性当前前缀和-以前前缀和=target <=> 以前前缀和=当前前缀和-target。

把这个思路搬到树上来写，其中哈希表记录的是一条根到当前节点的路径

class Solution {
public:
    unordered_map<long long,int> prefixCount;
    long long target;
    int dfs(TreeNode* root,long long currentSum){
        if(!root) return 0;
        currentSum+=root->val;
        int ans=prefixCount[currentSum-target];
        prefixCount[currentSum]++;
        ans+=dfs(root->left,currentSum);
        ans+=dfs(root->right,currentSum);
        prefixCount[currentSum]--;
        return ans;
    }
    int pathSum(TreeNode* root, int targetSum) {
        target=targetSum;
        prefixCount[0]=1;
        return dfs(root,0);
    }
};

其实前缀和的解法倒也不是很难写，只要能够注意到路径之和刚好是一种前缀和后面就可以顺理成章的往下写了～

236. 二叉树的最近公共祖先

本题要求给两个节点找公共祖先，其中节点可以是自己的祖先。

最省脑子的偷鸡思路就是先看一个节点是否是另一个节点的祖先节点，如果是，直接返回该祖先节点（结果发现这种情况剪枝好像可以剪掉）；如果不是，从根往下依次遍历，什么时候无法在遍历结果中同时找到两个节点，则上一个节点就是其最近公共祖先。

class Solution {
public:
    bool contains(TreeNode* root, TreeNode* target){
        if(!root) return false;
        if(root==target) return true;
        return contains(root->left , target) || contains(root->right , target);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p || root==q) return root;

        bool pInLeft=contains(root->left,p);
        bool qInLeft=contains(root->left,q);

        if(pInLeft && qInLeft) {
            return lowestCommonAncestor(root->left,p,q);
        }
        if(!pInLeft && !qInLeft){
            return lowestCommonAncestor(root->right,p,q);
        }
        return root;
    }
};

但是这种方法会重复扫描很多节点，最差的时间复杂度会达到O(n²)

优化方法可以用后序遍历来做，这同样是一种很直观的想法，后续遍历是一路找到最下面开始，倒放一下就是自然的从左右两边往上捋，唯一的难点是这个递归有一点难写（

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr) return nullptr;
        if (root == p || root==q) return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left != nullptr && right!=nullptr) return root;
        if(left != nullptr) return left;
        return right;
    }
};

124. 二叉树中的最大路径和

本题的节点值含有负数，要求给出最大路径和，其实和前面的求二叉树的直径非常类似，依然是一个后序遍历的思路，但是由于负数节点的存在，我们拉一个概念叫贡献出来，负数节点对于路径和的贡献为 0。

需要特别注意的地方是在后序遍历往上拔（返回）的时候只能选择一边从而避免交叉而不是一条线。

class Solution {
public:
    int ans=INT_MIN;
    int dfs(TreeNode* root){
        if(!root) return 0;
        
        int leftGain=max(0,dfs(root->left));
        int rightGain=max(0,dfs(root->right));
        
        ans=max(root->val + leftGain + rightGain , ans);

        return root->val + max(leftGain,rightGain);
    }
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

本文由 lbyxiaolizi 原创

采用 CC BY-NC-SA 4.0 协议进行许可

转载请注明出处：https://blog.vh.gs/cs/binary-tree-medium.html

标签: 算法 数据结构

相关推荐

0 评论

发表评论