1.Algorithm

107. 二叉树的层次遍历 II

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> arr = new ArrayList<Integer>();
            for(int i = 0;i<size; i++){
                TreeNode t = queue.poll();
                arr.add(t.val);
                TreeNode leftt = t.left;
                TreeNode rightt = t.right;
                if (leftt != null) queue.offer(leftt);
                if (rightt != null) queue.offer(rightt);
            }
            levelOrder.add(0, arr);
        }
        return levelOrder;
    }
}

2.Review

Data Structure and Algorithms - Stack
堆栈是一种抽象数据类型(ADT)，通常在大多数编程语言中使用。它被命名为堆栈，因为它表现的类似于真实世界的堆栈，例如-一副牌或一堆碟子，等等。

真实的堆栈只允许在一端进行操作。例如，我们可以从堆栈的顶部放置或移除一张牌或盘子。同样，堆栈ADT只允许在一端进行所有数据操作。在任何给定的时间，我们只能访问堆栈的顶部元素。

这个特性使它成为后进先出的数据结构。LIFO代表后进先出。在这里，最后放置(插入或添加)的元素首先被访问。在栈术语中，插入操作称为PUSH操作，删除操作称为POP操作。

堆栈呈现

下面的图表描述了一个堆栈和它的操作

堆栈可以通过数组、结构、指针和链表来实现。堆栈可以是固定大小的，也可以是动态调整大小的。在这里，我们将使用数组来实现堆栈，这使得它成为一个固定大小的堆栈实现。

基本操作

堆栈操作可能包括初始化堆栈，使用它，然后取消初始化。除了这些基本的东西，堆栈用于以下两个主要的操作-

push() − Pushing (storing) an element on the stack.
pop() − Removing (accessing) an element from the stack.

当数据被压入堆栈时。

为了有效地使用堆栈，我们还需要检查堆栈的状态。出于同样的目的，下面的功能操作被添加到堆栈−

peek() − get the top data element of the stack, without removing it.
isFull() − check if stack is full.
isEmpty() − check if stack is empty.

在任何时候，我们都维护一个指针指向堆栈上最后推送的数据。因为这个指针总是表示堆栈的顶部，因此被命名为top。top指针提供堆栈的top值，而不实际删除它。

首先我们要学习程序来支持堆栈函数
peek()
Algorithm of peek() function −

begin procedure peek
   return stack[top]
end procedure

在C语言中实现peek()函数
示例

int peek() {
   return stack[top];
}

isfull()
Algorithm of isfull() function −

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

在C语言中实现isfull()函数
示例

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

isempty()
Algorithm of isempty() function −

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif
   
end procedure

在C编程语言中实现isempty()函数略有不同。我们将top初始化为-1，因为数组中的索引从0开始。因此，我们检查top是否小于0或-1，以确定堆栈是否为空。这是它的代码
示例

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

推入操作

将新数据元素放到堆栈上的过程称为Push操作。Push操作包括一系列的步骤-

Step 1 − 检查堆栈是否满了。
Step 2 − 如果满了，产生一个错误并中断。
Step 3 − 如果没满,新增top指向下一个空的空间。
Step 4 − 添加数据元素到top指向的堆栈位置。
Step 5 − 返回成功。

如果使用链表来实现堆栈，那么在步骤3中，我们需要动态地分配空间。
PUSH 操作算法
push操作通过一个简单算法可以推导如下：

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data

end procedure

用C语言实现这个算法，非常简单。参见以下代码-
示例：

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

出栈操作

从栈中移除访问的内容被称作出栈操作。在一个数组中实现pop()操作，数据元素实际上并没有被删除，而是将top递减到指向堆栈中下一个更低的位置。但在链表实现中，pop()实际上删除数据元素并释放内存空间。
出栈操作可以包括以下步骤：

Step 1 − 检查堆栈是否为空。
Step 2 − 如果是空了，产生一个错误并中断。
Step 3 − 如果堆栈不是空的，则访问顶部所指向的数据元素。
Step 4 − 将top的值减少1。。
Step 5 − 返回成功。

Pop操作通过一个简单算法可以推导如下：

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

用C语言实现这个算法，非常简单。参见以下代码-
示例：

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

用C语言实现一个完整的stack程序，请点击这里

3.Tips

如何将思想组织成金字塔结构：

归类分组-》找出逻辑关系，抽象概括-》金字塔形式转换

金字塔结构每个节点概括来讲有3种形式（纵向(向上/向下)，横向）

纵向-向上/向下：位于一组思想的上一个层次的思想是对这一级思想的概括，这一组思想则是对其上一层次思想的解释和支持。文章中任一层次上的思想必须是其下一层次思想的概括。
横向：每组中的思想必须属于同一逻辑范畴。
横向：每组中的思想必须按逻辑顺序组织。
4种逻辑顺序：
- 演绎顺序：大前提、小前提、结论
- 时间（步骤）顺序：第一、第二、第三
- 结构（空间）顺序：北京、上海、深圳
- 程度（重要性）顺序：最重要、次重要、等等

自上而下表达，结论先行/自下而上思考，总结概括
如果作者传达给读者的思想已经事先进行了归类和概括，并且按自上而下的顺序呈现，读者就能更容易理解作者表达的思想。这样方能条理清晰。

演绎推理、发现因果关系、化整为零和归纳总结是大脑可进行行的公有4种分析活动，这4种顺序也是大脑可用于组织思想的仅有的4种顺序。

4.Share

本周分享三句话：

世界之所以是这样的构成，取决于你的认知--》康德（德国古典哲学创始人）
认知，几乎是人和人之间唯一的本质差别：技能的差别是可量化的，技能再多累加，也就是熟练工种，而认知的差别是本质的，是不可量化的
世界唯一不变的就是变化，对于长期趋势的不同认知直接决定着有什么样的布局

感悟：
最近在学习之前了解的技术，可能得益于自己这几年认知能力的提升，之前觉得很难的东西，现在看起来，觉得挺容易。

ARTS第13周