剑指offer-树2e2m-7

剑指offer-树2e2m-7,第1张

剑指offer-树2e2m-7

目录

[JZ82 (e)二叉树中和为某一值的路径(一)][1][JZ34 (m)二叉树中和为某一值的路径(二)][2][JZ36 (m)二叉搜索树与双向链表][3][JZ79 (e)判断是不是平衡二叉树][4]今天学到的知识


JZ82 (e)二叉树中和为某一值的路径(一)

递归,cur存当前节点的val总和
注意,此处的cur传入的是一个值,对于每一次的dfs调用,其都被复制了一次,所以在dfs返回时不需要处理cur;若传入的是一个引用,就需要考虑在dfs返回时将其恢复原状复杂度:时间 O ( n ) O(n) O(n),空间 O ( n ) O(n) O(n)(递归调用栈)

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        return dfs(root, 0, sum);
    }
    
    bool dfs(TreeNode *root, int cur, int sum){
        if(!root) return false;
        cur+=root->val;
        if(cur==sum && !root->left && !root->right) return true;
        return dfs(root->left, cur, sum) || dfs(root->right, cur, sum);
    }
};
JZ34 (m)二叉树中和为某一值的路径(二)

递归,类似上一题,但是此时就要考虑恢复原状的问题了复杂度:时间 O ( n ) O(n) O(n),空间 O ( n ) O(n) O(n)(递归调用栈+两个vector)

#include 
class Solution {
public:
    vector> FindPath(TreeNode* root,int expectNumber) {
        vector > ret;
        vector cur;
        dfs(root, cur, expectNumber, ret);
        return ret;
    }
    
    void dfs(TreeNode *root, vector &cur, int sum, vector > &ret){
        if(!root) return;
        cur.push_back(root->val);
        if(accumulate(cur.begin(), cur.end(), 0) ==sum && !root->left && !root->right) {
            ret.push_back(cur);
        }
        dfs(root->left, cur, sum, ret);
        dfs(root->right, cur, sum, ret);
        cur.pop_back();// 恢复原状
    }
};
JZ36 (m)二叉搜索树与双向链表

树的中序遍历,使用一个指针preNode指向当前考察结点的前一结点复杂度:时间 O ( n ) O(n) O(n),空间 O ( n ) O(n) O(n)(递归调用栈)

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(!pRootOfTree) return nullptr;
        TreeNode *preNode=nullptr;
        TreeNode *ret=pRootOfTree;
        
        while(ret->left) ret=ret->left;
        inorder(pRootOfTree, preNode);
        return ret;
    }
    
    void inorder(TreeNode *root, TreeNode* &preNode){
        if(!root) return;
        // 左树
        inorder(root->left, preNode);
        // 左树处理完成意味着左树根节点可以修改了
        root->left=preNode;
        if(preNode) preNode->right = root;
        // 修改preNode
        preNode = root;
        // 右树
        inorder(root->right, preNode);
    }
};
JZ79 (e)判断是不是平衡二叉树

递归到叶子节点,然后在回溯的过程中来判断是否满足条件

复杂度:时间 O ( n ) O(n) O(n),空间 O ( n ) O(n) O(n)(递归调用栈)

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return height(pRoot)!=-1;
    }
    
    int height(TreeNode *root){
        if(!root) return 0;
        int l,r;
        if((l=height(root->left))==-1) return -1;
        if((r=height(root->right))==-1) return -1;
        if(abs(l-r)>1) return -1;
        return max(l,r)+1;
    }
};
今天学到的知识

std::accumulate(first, last, init)std::copy(first, last, d_first)

d_first - the beginning of the destination range.如果拷贝目标是一个container,d_first = std::back_inserter(container &c);

std::copy(from_vector.begin(), from_vector.end(),
              std::back_inserter(to_vector));
还可以将容器内元素拷贝到标准输出:
std::copy(to_vector.begin(), to_vector.end(),
              std::ostream_iterator(std::cout, " "));

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5702904.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存