二叉樹的遍歷方式

1. 深度優(yōu)先遍歷

• 前序遍歷：根、左、右（遞歸法、迭代法）
• 中序遍歷：左、根、右（遞歸法、迭代法）
• 后序遍歷：左、右、根（遞歸法、迭代法）

舉例：

image.png

前序遍歷：5、4、1、2、6、7、8
中序遍歷：1、4、2、5、7、6、8
后序遍歷：1、2、4、7、8、6、5

2. 廣度優(yōu)先遍歷

• 層次遍歷（迭代法）

二叉樹的存儲方式

二叉樹可以鏈式存儲，也可以順序存儲

• 鏈式存儲：利用指針，通過指針把分布在各個地址的節(jié)點串聯(lián)起來
• 順序存儲：利用數(shù)組，存儲的元素在內(nèi)存是連續(xù)分布的
  用上圖二叉樹舉例說明一下順序存儲
  如果父節(jié)點的數(shù)組下標是，那么左節(jié)點的數(shù)組下標是 i * 2+1，右節(jié)點的數(shù)組下標是 i * 2+2。
  
  image.png

144. 二叉樹的前序遍歷

遞歸實現(xiàn)

var preorderTraversal = function(root) {
    let res = [];
    var traversal = function(cur) {
      if (cur === null) {
        return
      }
      res.push(cur.val)
      traversal(cur.left)
      traversal(cur.right)
    }
    traversal(root)
    return res;
};

迭代實現(xiàn)

• 由于前序遍歷是先根，后左右節(jié)點。所以優(yōu)先存儲根節(jié)點，再依次存儲右節(jié)點、左節(jié)點，將左節(jié)點放在后面，這樣在彈出節(jié)點時的順序才會是先左節(jié)點，再右節(jié)點。

var preorderTraversal = function(root) {
    if (!root) return []
    let res = [];
    let stack = [];
    stack.push(root)
    while(stack.length) {
        let cur = stack.pop()
        res.push(cur.val)
        if (cur.right) {
            stack.push(cur.right)
        }
        if (cur.left) {
            stack.push(cur.left)
        }
    }
    return res;
};

94. 二叉樹的中序遍歷

遞歸實現(xiàn)

var inorderTraversal = function(root) {
    let res = [];
    var traversal = function(root) {
        if (root === null) {
            return
        }
        traversal(root.left);
        res.push(root.val)
        traversal(root.right);
    }
    traversal(root)
    return res;
};

迭代實現(xiàn)

• 與前序遍歷不同，中序遍歷需要優(yōu)先拿到左節(jié)點。
• 先訪問的是二叉樹頂部的節(jié)點，然后一層一層向下訪問，直到到達樹左面的最底部，再開始處理節(jié)點（也就是在把節(jié)點的數(shù)值放進結(jié)果數(shù)組中）。

var inorderTraversal = function(root) {
    let res = [];
    // 迭代遍歷 左中右
    let cur = root;
    let stack = [];
    while (cur !== null || stack.length) {
        if (cur !== null) {
            stack.push(cur)
            cur = cur.left
        } else {
            cur = stack.pop()
            res.push(cur.val)
            cur = cur.right
        }
    }
    return res;
};

145. 二叉樹的后序遍歷

遞歸實現(xiàn)

var postorderTraversal = function(root) {
    let res = [];
    var traversal = function(root) {
        if (root === null) {
            return
        }
        traversal(root.left);
        traversal(root.right);
        res.push(root.val)
    }
    traversal(root)
    return res;
};

迭代實現(xiàn)

• 與前序遍歷相似，可以轉(zhuǎn)換遍歷順序為根、右、左，再將其結(jié)果返回即可。

var postorderTraversal = function(root) {
    if (!root) return []
    let res = [];
    let stack = [];
    stack.push(root)
    while(stack.length) {
        let cur = stack.pop()
        res.push(cur.val)
        if (cur.left) {
            stack.push(cur.left)
        }
        if (cur.right) {
            stack.push(cur.right)
        }
    }
    return res.reverse();
};