前端程式員學好演算法系列（五）棧和隊列

1.棧的基礎使用，js中數組直接可以作為棧使用，棧遵循先進後出的原則，即js可以使用push()和pop() 比較容易的實現一個棧

20. 有效的括弧
給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字元串，判斷字元串是否有效。

有效字元串需滿足：

左括弧必須用相同類型的右括弧閉合。
左括弧必須以正確的順序閉合。

示例 1:
輸入: "()"
輸出: true


示例 2:
輸入: "()[]{}"
輸出: true

解題：

1.我們定義obj 對應括弧的另一半
2.我們定義一個棧stack
3.迴圈字元串當字元串為前括弧時入棧

4.當s[i] 為後括弧時我們先判斷stack.length是否為0，為0返回false ，不為0我們取出棧頂的元素，借用obj進行比較不相等是返回false
5.當遍歷結束後，如果stack.length為0時說明可以匹配

var isValid = function(s) {
    let obj = {'{':'}','[':']','(':')'}
    let stack = []
    for(let i = 0;i<s.length;i++){
        if(s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{'){
            stack.push(s.charAt(i))
        } else {
            if(stack.length>0){
              let c = stack.pop()
              if(obj[c]!==s[i]){
                return false
              }
            }else{
                return false
            }  
        }
    }
    if(stack.length==0){
        return true
    } else {
        return false
    }
};

71. 簡化路徑
以 Unix 風格給出一個文件的絕對路徑，你需要簡化它。或者換句話說，將其轉換為規範路徑。

在 Unix 風格的文件系統中，一個點（.）表示當前目錄本身；此外，兩個點 （..） 表示將目錄切換到上一級（指向父目錄）；兩者都可以是複雜相對路徑的組成部分。更多信息請參閱：Linux / Unix中的絕對路徑 vs 相對路徑

請註意，返回的規範路徑必須始終以斜杠 / 開頭，並且兩個目錄名之間必須只有一個斜杠 /。最後一個目錄名（如果存在）不能以 / 結尾。此外，規範路徑必須是表示絕對路徑的最短字元串。
示例 1：

輸入："/home/"
輸出："/home"

解釋：註意，最後一個目錄名後面沒有斜杠。
示例 2：

輸入："/../"
輸出："/"
解釋：從根目錄向上一級是不可行的，因為根是你可以到達的最高級。

解題：
1.我們用/ 把路徑拆分為數組並去除空值
2.token[i] 為..時我們刪除結尾的元素
3.token[i] 為.是不做處理 否則加入棧
4.返回元素

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
      const stack = []
      let token = path.split('/').filter(a=>a)
      for(let i=0;i<token.length;i++){
           if(token[i]=='..'){
             stack.pop()
           } else if(token[i]=='.'){
           } else {
             stack.push(token[i])
           }
      }
      return '/'+stack.join('/')
};

145. 二叉樹的後序遍歷
給定一個二叉樹，返回它的 後序 遍歷。

示例:

輸入: [1,null,2,3] 
1
\
2
/
3

輸出: [3,2,1]

解題一：

系統的遞歸本身就是由棧實現的，我們先用遞歸的方式求下解：
1.root為null時直接返回null
2.定義儲存數組的值result, 我們在pushRoot中遞歸調用root.left 和root.right  在push node.val 的值。
3.返回result

var postorderTraversal = function(root) {   
    var result = [];
    function pushRoot(node){
        if(node != null){
            if(node.left != null){
                pushRoot(node.left);
            }
            if(node.right != null){
                pushRoot(node.right);
            } 
            result.push(node.val);
        }
    }
    pushRoot(root);
    return result;
            
};

解題二.
1.root為null時直接返回null

2.我們定義一個棧popo 裡面預設存放node為root type為1為儲存的節點對象 type為2時代表存儲的節點值

3.如果棧中存在值 我們就取最尾部的值，如果該值存在left和right節點我們就取出來存入棧中
4.重點：我們後序遍歷的遍歷順序為 left right 取值val 入棧的順序就為 val right left 這一部分順後我在詳細說明下。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    
    let res = []   
    if(root==null){
      return []
    }
    let popo = [{type:1,node:root}]
    while(popo.length){
        const { type, node }= popo.pop()
        if(type==2){
           res.push(node)
        } else {
            popo.push({type:2,node:node.val})
            if(node.right){
              popo.push({type:1,node:node.right})
            }
            if(node.left){
              popo.push({type:1,node:node.left})
            }
        }
    }
    return res
};