算法：二叉树

本文简单梳理二叉树相关话题

一： 二叉树的遍历

1. 前序遍历: 根左右

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 */
function preorderTraversal( root ) {
  function preOrder(root){
    if(root == null)  return;
    res.push(root.val);
    preOrder(root.left);
    preOrder(root.right);
  }
  let res = [];
  preOrder(root);
  return res;
    // write code here
}
module.exports = {
    preorderTraversal : preorderTraversal
};

2. 中序遍历： 左根右

   function inorderTraversal( root ) {
       // write code here
       const walk = (node) => {
           if (!node) return 
           walk(node.left)
           res.push(node.val)
           walk(node.right)
       }
       const res = []
       walk(root)
       return res
   }

3. 后序遍历: 左右根

   function postorderTraversal( root ) {
       // write code here
       const walk = (node) => {
           if (!node) return
           walk(node.left)
           walk(node.right)
           res.push(node.val)
       }
       const res = []
       walk(root)
       return res
   }

4. 层次遍历

function levelOrder( root ) {
    // write code here
    if (!root) return []
    const queue = []
    const res = []
    queue.push(root)
    let level = 0
    while(queue.length) {
        const size = queue.length
        const temp = []
        for (let i = 0; i < size; i++) {
            const node = queue.shift()
            temp.push(node.val)
            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
        }
        res.push(temp)
    }

    return res
}

二： 二叉树最大深度

1. 遍历

   function maxDepth( root ) {
       // write code here
       if (!root) return 0
       const queue = [root]
       const res = []
       while (queue.length) {
           const size = queue.length
           const temp = []
   
           for (let i = 0; i < size; i++) {
               const node = queue.shift()
               temp.push(node.val)
               if (node.left) queue.push(node.left)
               if (node.right) queue.push(node.right)
           }
           res.push(temp)
       }
       return res.length
   }

2. 递归

   function maxDepth( root ) {
       if (root == null) return 0
       return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
   }