代码随想录训练营Day14 | 二叉树遍历

二叉树的遍历方式

1. 深度优先遍历

• 前序遍历：根、左、右（递归法、迭代法）
• 中序遍历：左、根、右（递归法、迭代法）
• 后序遍历：左、右、根（递归法、迭代法）

举例：

image.png

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

2. 广度优先遍历

• 层次遍历（迭代法）

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储

• 链式存储：利用指针，通过指针把分布在各个地址的节点串联起来
• 顺序存储：利用数组，存储的元素在内存是连续分布的
  用上图二叉树举例说明一下顺序存储
  如果父节点的数组下标是，那么左节点的数组下标是 i * 2+1，右节点的数组下标是 i * 2+2。
  
  image.png

144. 二叉树的前序遍历

递归实现

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;
};

迭代实现

• 由于前序遍历是先根，后左右节点。所以优先存储根节点，再依次存储右节点、左节点，将左节点放在后面，这样在弹出节点时的顺序才会是先左节点，再右节点。

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. 二叉树的中序遍历

递归实现

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;
};

迭代实现

• 与前序遍历不同，中序遍历需要优先拿到左节点。
• 先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进结果数组中）。

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. 二叉树的后序遍历

递归实现

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;
};

迭代实现

• 与前序遍历相似，可以转换遍历顺序为根、右、左，再将其结果返回即可。

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();
};