leetcode 10.19-10.25

2020-10-18

19 删除链表的倒数第N个节点
107 二叉树的层次遍历II

19. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：先用一个指针$tail$指向第$n$个节点，然后指针$p$从$head$开始与$tail$一同遍历链表，直到$tail$指向链表的最后一个节点，此时$p$指向的是被删除节点的前一个节点，删除对应节点即可。需要注意的是，如果$tail$在第一次遍历中指向$None$，说明被删除的节点是链表的头节点。

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        tail = head
        for i in range(n):
            tail = tail.next
        if tail is None:
            return head.next
        p = head
        while tail.next is not None:
            p = p.next
            tail = tail.next
        p.next = p.next.next
        return head

107. 二叉树的层序遍历II

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：比较简单，广度优先遍历，先从上到下记录节点，遍历完之，reverse下结果向量，返回即可

AC代码：

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == NULL) 
            return ret;
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int len = q.size();
            vector<int> level;
            for (int i = 0; i < len; i++) {
                auto p = q.front();
                level.push_back(p->val);
                q.pop();
                if (p->left)  q.push(p->left);
                if (p->right) q.push(p->right);
            }
            ret.push_back(level);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};