leetcode每日一题42

107.二叉树的层序遍历II

就层序遍历后reverse一下

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        if(root!=nullptr)
            que.push(root);
        vector<vector<int>> result;
        while(!que.empty()){
            int size=que.size();
            vector<int> vec;
            for(int i=0;i<size;i++)
            {
                TreeNode* node=que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

109. 有序链表转换二叉搜索树

先用快慢指针找中点，再递归构造二叉搜索树
类似二分

class Solution {
public:
    ListNode* midNode(ListNode* left,ListNode* right){
        ListNode *fast,*slow;
        fast=left;
        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=midNode(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);//左闭右开区间
    }
};

113. 路径总和 II

112是返回有没有总和为给定值的路径，这道题是返回所有总和为给定值的路径
因此要遍历整个树，找到所有路径，且不用处理递归返回值，所以递归函数不要返回值！

1. 确定递归函数的参数和返回类型
   需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型

void traversal(TreeNode* cur, int count) 

2. 确定终止条件
   让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
   如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
   如果遍历到了叶子节点，count不为0，就是没找到。

if(count==0&&!cur->left&&!cur->right){
	result.push_back(path);
	return;
}
else if (!cur->left && !cur->right)
	return;

3. 确定单层递归的逻辑
   如果子节点不为空，加入path，count减去子节点值，递归，递归结束后，回溯，count加回来，去除path中的子节点

if(cur->left)
{
    path.push_back(cur->left->val);
    count-=cur->left->val;
    traversal(cur->left,count);
    count+=cur->left->val;
    path.pop_back();
}
if(cur->right)
{
    path.push_back(cur->right->val);
    count-=cur->right->val;
    traversal(cur->right,count);
    count+=cur->right->val;
    path.pop_back();
}

整体代码

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void traversal(TreeNode* cur, int count) 
    {
        if(count==0&&!cur->left&&!cur->right){
            result.push_back(path);
            return;
        }
        else if (!cur->left && !cur->right)
            return;
        if(cur->left)
        {
            path.push_back(cur->left->val);
            count-=cur->left->val;
            traversal(cur->left,count);
            count+=cur->left->val;
            path.pop_back();
        }
        if(cur->right)
        {
            path.push_back(cur->right->val);
            count-=cur->right->val;
            traversal(cur->right,count);
            count+=cur->right->val;
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        result.clear();
        path.clear();
        if (root == NULL) return result;
        path.push_back(root->val); // 把根节点放进路径
        traversal(root, targetSum - root->val);
        return result;
    }
};

114. 二叉树展开为链表

这不就是前序遍历
其实要做的就是按前序序列创建一个树，每个节点只有右子树