二叉树基础

树
- 树是一种常用的数据结构，用来模拟具有树状结构性质的数据集合
- 树的每一个节点有一个根植和一个包含所有子节点的列表。
二叉树
- 二叉树是一种更为典型的树状结构。二叉树每个节点最多具有两个子树，通常子树称为“左子树”和“右子树”
二叉树前序遍历
- 前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树（根节点 -> 左子树 -> 右子树）
- 算法：

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/

//  递归
const preorderTraversal = function(root) {
   let result = []
   function fn(root){
       if(root !== null){
           result.push(root.val)
           if(root.left) fn(root.left)
           if(root.right) fn(root.right)
       }
   }
   fn(root)
   return result
};

二叉树中序遍历
- 先遍历左子树，然后访问根节点，最后遍历右子树（左子树 -> 根节点 -> 右子树）
- 算法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

const inorderTraversal = function(root) {
    let result = []
    function fn(root){
        if(root !== null){
            if(root.left) fn(root.left)
            result.push(root.val)
            if(root.right) fn(root.right)
        }
    }
    fn(root)
    return result
};

二叉树后序遍历
- 先遍历左子树，然后遍历右子树，最后访问根节点（左子树 -> 右子树 -> 根节点）
- 算法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const postorderTraversal = function(root) {
    let result = []
    function fn(root){
        if(root !== null){
            if(root.left) fn(root.left)
            if(root.right) fn(root.right)
            result.push(root.val)
        }
    }
    fn(root)
    return result
};

二叉树层序遍历
- 算法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */

// 广度优先 前序
const levelOrder = function(root) {
    let levels = []
    if(root === null) return levels
    function fn(node, level){
        let len = levels.length
        if(len === level) levels.push([]) 
        levels[level].push(node.val)
        if(node.left) fn(node.left, level+1)
        if(node.right) fn(node.right, level+1)
    }
    fn(root, 0)
    return levels
};

二叉树最大深度
- 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数
- 算法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    // 写递归的一个重要思路就是相信这个函数能完成任务，此题带有动态规划的感觉
    // 最大深度 = 1+Math.max(根节点的左子树最大深度, 根节点的右子树最大深度)
    // 根节点的左子树最大深度 = 1 + Math.max(左子树的左子树最大深度, 左子树的右子树最大深度)
    // 根节点的右子树最大深度 = 1 + Math.max(右子树的左子树最大深度, 右子树的右子树最大深度)
    if(!root){
        return 0
    }else{
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
    }
};

对称二叉树
- 给定一个二叉树，检查它是否是镜像对称的。
- 算法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    return isMirroTree(root, root)
};

function isMirroTree(root_1, root_2){
    if(root_1 === null && root_2 === null) return true
    if(root_1 === null || root_2 === null) return false
    return (root_1.val === root_2.val) && isMirroTree(root_1.left, root_2.right) && isMirroTree(root_1.right, root_2.left)
}

路径总和
- 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
- 说明: 叶子节点是指没有子节点的节点。
- 算法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    return helper(root, sum)
};

function helper(node, sum){
    if(!node){
        return false
    }else{
        sum -= node.val
    }
    if(!node.left && !node.right){
        return sum === 0
    }
    return helper(node.left, sum) || helper(node.right, sum)
}