剑指offer-树2e2m-7

剑指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, " "));