二叉树的递归遍历

先序遍历

// 所有遍历函数的入参都是树的根结点对象
function preorder(root) {
  // 递归边界，root 为空
  if(!root) {
    return 
  }
  // 输出当前遍历的结点值
  console.log('当前遍历的结点值是：', root.val)  
  // 递归遍历左子树 
  preorder(root.left)  
  // 递归遍历右子树  
  preorder(root.right)
}

中序遍历

// 所有遍历函数的入参都是树的根结点对象
function inorder(root) {
  // 递归边界，root 为空
  if(!root) {
    return 
  }
  // 递归遍历左子树 
  inorder(root.left)  
  // 输出当前遍历的结点值
  console.log('当前遍历的结点值是：', root.val)  
  // 递归遍历右子树  
  inorder(root.right)
}

后序遍历

function postorder(root) {
  // 递归边界，root 为空
  if(!root) {
    return 
  }
  // 递归遍历左子树 
  postorder(root.left)  
  // 递归遍历右子树  
  postorder(root.right)
  // 输出当前遍历的结点值
  console.log('当前遍历的结点值是：', root.val)  
}

二叉树的迭代遍历

先序遍历-144

给你二叉树的根节点 root ，返回它节点值的前序遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

中序遍历

中序遍历的是顺序是： 左 -> 根 -> 右。如果我们要对下面这棵树进行中序遍历就需要找到最左边的节点 D，在找节点 D 的时候途中会经过 节点 A、B。我们把这些经过的节点按照经过的顺序推入栈中，这样最终栈顶元素就是这棵树最左边的节点。当遍历完最左孩子后，将它弹出，这时栈顶元素就是这个最左节点的父节点，遍历完这个父节点也就是遍历了根节点，通过这个父节点我们可以很轻松的遍历它的右孩子，这样我们就完成了对这个节点的中序遍历，如此反复完成整棵树的中序遍历。

代码实现：

const root = {
  val: 'A',
  left: {
      val: 'B',
      left: {
          val: 'D'
      },
      right: {
          val: 'E'
      }
  },
  right: {
      val: 'C',
      right: {
          val: 'F'
      },
  }
}
function inorder(root) {
  if (!root) return root;
  // 初始结果数据和定义栈结构
  const stack = [], res = [];
  // 游标，用力遍历节点
  let cur = root;
  while (cur || stack.length) {
    // 寻找最左叶子节点，并把经过的节点记录下来
    while (cur) {
      // 将经过的节点存入栈
      stack.push(cur);
      // 继续查找左子树
      cur = cur.left;
    }
    // 取出栈顶元素
    cur = stack.pop();
    // 将栈顶元素的结果值存入到 res 数组中
    res.push(cur.val);
    // 读取栈顶元素的右子树
    cur = cur.right;
  }
  return res;
}

console.log(inorder(root)); // ["D", "B", "E", "A", "C", "F"]

后序遍历

const root = {
  val: 'A',
  left: {
      val: 'B',
      left: {
          val: 'D'
      },
      right: {
          val: 'E'
      }
  },
  right: {
      val: 'C',
      right: {
          val: 'F'
      },
  }
}
function postorder(root) {
  if (!root) return root;
  const stack = [];
  const res = [];
  stack.push(root);
  while (stack.length) {
    const cur = stack.pop();
    res.unshift(cur.val);
    if (cur.left) stack.push(cur.left);
    if (cur.right) stack.push(cur.right);
  }
  return res;
}

console.log(postOrder(root)); // ["D", "E", "B", "F", "C", "A"]

二叉树的层序遍历

function BFS(root) {
    if (!root) return root;
    const queue = [];
    queue.push(root);
    while (queue.length) {
        const top = queue.shift();
        console.log(top.val);
        if (top.left) queue.push(top.left);
        if (top.right) queue.push(top.right);
  }
}

翻转二叉树-226

思路：
翻转二叉树的思路比较简单，主要用到了递归。我们先获取二叉树的左子树，然后再获取二叉树的右子树，将两子树对调下，返回最终结果即可。

function invertTree(root) {
  // 如果节点为空则直接返回
  if (!root) return root;
  // 获取左子树
  const left = invertTree(root.left);
  // 获取右子树
  const right = invertTree(root.right);
  // 将右子树赋值给左子树
  root.left = right;
  // 将左子树赋值给右子树
  root.right = left;
  // 返回交换后的结果
  return root;
}

二叉树的层序遍历-102

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。



示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]


提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

const levelOrder = function(root) {
    // 初始化结果数组
    const res = []  
    // 处理边界条件
    if(!root) {
        return res
    }  
    // 初始化队列
    const queue = []   
    // 队列第一个元素是根结点
    queue.push(root)  
    // 当队列不为空时，反复执行以下逻辑
    while(queue.length) {
        // level 用来存储当前层的结点
        const level = []  
        // 缓存刚进入循环时的队列长度，这一步很关键，因为队列长度后面会发生改变
        const len = queue.length  
        // 循环遍历当前层级的结点
        for(let i=0;i<len;i++) {
            // 取出队列的头部元素
            const top = queue.shift()  
            // 将头部元素的值推入 level 数组
            level.push(top.val)
            // 如果当前结点有左孩子，则推入下一层级
            if(top.left) {
                queue.push(top.left)
            }
            // 如果当前结点有右孩子，则推入下一层级
            if(top.right) {
                queue.push(top.right)
            }
        }
        // 将 level 推入结果数组
        res.push(level)
    }
    // 返回结果数组
    return res
};

⼆叉树的层序遍历Ⅱ-107

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题和上面那道题的解法是很类似，只不过在最后添加的时候有点区别。

var levelOrderBottom = function(root) {
  const res = [];
  if (!root) return res;
  const queue = [];
  queue.push(root);
  while (queue.length) {
    const level = [];
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.unshift(level);
  }
  return res;
};

二叉搜索树中查找某个元素

const root = {
    val: 6,
    left: {
        val: 3,
        left: {
            val: 1
        },
        right: {
            val: 4
        }
    },
    right: {
        val: 8,
        left: {
            val: 7
        },
        right: {
            val: 9
        }
    }
};

function search(root, val) {
  // 节点为空，直接返回
    if (!root) return root;
  // 当前节点的值和查找的值相等，直接返回当前节点的值
    if (val == root.val) {
        return root.val;
    }else if (val < root.val) { // 当前节点的值大于查找值，则向左子树继续查找
        return search(root.left, val);
    }else { // 当前节点的值小于查找的值，则向右子树继续查找
        return search(root.right, val);
    }
}

二叉搜索树中添加某个元素

const root = {
    val: 6,
    left: {
        val: 3,
        left: {
            val: 1
        },
        right: {
            val: 4
        }
    },
    right: {
        val: 8,
        left: {
            val: 7
        },
        right: {
            val: 9
        }
    }
};
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}
function insert(root, val) {
  // 
    if (!root) return new TreeNode(val);
  // 插入的值小于当前节点，则继续向左子树寻找位置插入
    if (val < root.val) {
        root.left = insert(root.left, val);
    } else { // 插入的值大于当前节点，则继续向右子树寻找位置插入
        root.right = insert(root.right, val);
    }
  // 返回最终结果
    return root;
}

二叉搜索树中删除某个元素

function deleteNode(root, key) {
  // 没有找到要删除的节点，直接返回 null
  if (!root) return null;
  // 当前节点的值和要删除的值相等
  if (root.val === key) {
    // 处理待删除节点没有左子树的情况
    if (!root.left) return root.right;
    // 处理待删除节点没有右子树的情况
    if (!root.right) return root.left;

    // 处理待删除节点左右子树都有的情况

    // 缓存待删除节点的右子树
    let node = root.right;
    // 在待删除节点的右子树中查找最小值节点
    while (node.left) {
      node = node.left;
    }
    // 将待删除节点的左子树赋值给待删除节点右子树的最小值节点的左子树上
    node.left = root.left;
    // 将待删除节点替换为待删除节点的右子树，完成删除
    root = root.right;
  }else if (root.val > key) { // 当前节点的值大于要删除的值，继续去左子树查找要删除的节点
    root.left = deleteNode(root.left, key);
  }else { // 当前节点的值小于要删除的值，继续去右子树查找要删除的节点
    root.right = deleteNode(root.right, key);
  }
  // 返回删除后的结果
  return root;
}

验证二叉搜索树-98

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
输入：root = [2,1,3]
输出：true

示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
我们可以利用二叉搜索树中序遍历是一个有序数组来判断它是不是一棵有效的二叉树搜索树。

var isValidBST = function (root) {
    const res = [];
    inorder(root);

    for (let i = 0, len = res.length - 1; i < len; i++) {
        if (res[i] >= res[i + 1]) return false;
    }
    return true;

    function inorder(root) {
        if (!root) return root;
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
};

var isValidBST = function (root) {
  let minValue = -Infinity;
  function inorder(root) {
    if (!root) return true;
    if (!inorder(root.left)) return false;
    if (root.val <= minValue) return false;
    minValue = root.val;
    return inorder(root.right);
  }
  return inorder(root);
};

将有序数组转为二叉搜索树-108

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。



示例 1：


输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：


输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。


提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

var sortedArrayToBST = function (nums) {
    const root = buildBST(0, nums.length - 1);

    function buildBST(low, high) {
      if (low > high) return null;
      const mid = Math.floor((low + high) / 2);
      const node = new TreeNode(nums[mid]);
      node.left = buildBST(low, mid - 1);
      node.right = buildBST(mid + 1, high);
      return node;
    }
    return root;
};

平衡二叉树的判定-110

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：

输入：root = []
输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

var isBalanced = function(root) {
  let flag = true;
  dfs(root);
  return flag;
  function dfs(root) {
    if (!root || !flag) return 0;
    let left = dfs(root.left);
    let right = dfs(root.right);
    if (Math.abs(left - right) > 1) {
      flag = false;
      return 0;
    }
    return Math.max(left, right) + 1;
  }
};

将二叉搜索树变平衡-1382

给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。

示例 1：

输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
示例 2：

输入: root = [2,1,3]
输出: [2,1,3]

提示：

树节点的数目在 [1, 104] 范围内。
1 <= Node.val <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balance-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：先使用中序遍历将二叉搜索树的值存入数组，得到一个升序数组，然后用这个数组的值构造平衡二叉树即可。

var balanceBST = function(root) {
  const res = [];
  inorder(root);
  return buildBST(0, res.length - 1);

  function buildBST(low, high) {
    if (low > high) return null;
    const mid = Math.floor(low + (high - low) / 2);
    const node = new TreeNode(res[mid]);
    node.left = buildBST(low, mid - 1);
    node.right = buildBST(mid + 1, high);
    return node;
  }
  // 二叉树的中序遍历，获取排序数组
  function inorder(root) {
    if (!root) return root;
    inorder(root.left);
    // 将遍历到的节点值存入数组
    res.push(root.val);
    inorder(root.right);
  }
};

从前序与中序遍历序列构造⼆叉树-105

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：
二叉树的先序遍历的第一个元素就是根节点的值。由此我们可以在中序遍历的数组里找到根元素所在的索引（重点，题目中说了二叉树中没有重复元素，如果有重复元素这个解法就不行了），根元素左边的为左子树的元素，根元素右边为右子树的元素。

在先序遍历中 [1, rootIndexInorder] 为左子树中的元素，[rootIndexInorder + 1, preorder.length-1] 为右子树的元素。

像上面这样，我们就通过根元素的索引，将先序遍历的结果和后续遍历的结果按照左右子树的元素拆分成了两部分，递归实现即可。

const buildNode = function (preorder, inorder) {
    if (!preorder.length) return null;

    const rootVal = preorder[0];
    const root = new TreeNode(rootVal);
    const index = inorder.indexOf(rootVal);
    const leftIn = inorder.slice(0, index);
    const rightIn = inorder.slice(index + 1);
    const leftPre = preorder.slice(1, index + 1);
    const rightPre = preorder.slice(index + 1);

    root.left = buildNode(leftPre, leftIn);
    root.right = buildNode(rightPre, rightIn);

    return root;
};

var buildTree = function (preorder, inorder) {
    return buildNode(preorder, inorder);
};

方法二：

function buildTree(preorder, inorder) {
    if (preorder.length === 0) {
        return null;
    }

    let i = 0;
    const map = buildMap(inorder);
    const helper = (start, end) => {
        if (start > end) {
            return null;
        }

        const root = new TreeNode(preorder[i]);
        const pivot = map.get(preorder[i]);

        i += 1;
        root.left = helper(start, pivot - 1);
        root.right = helper(pivot + 1, end);

        return root;
    }
    return helper(0, preorder.length - 1)
}

function buildMap(inorder) {
    const map = new Map();
    inorder.forEach((num, i) => {
        map.set(num, i);
    });
    return map;
}

N 叉树的前序遍历-589

给定一个 n 叉树的根节点  root ，返回 其节点值的前序遍历 。

n 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]
示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

提示：

节点总数在范围 [0, 104]内
0 <= Node.val <= 104
n 叉树的高度小于或等于 1000


进阶：递归法很简单，你可以使用迭代法完成此题吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首先请认真审题，这个是 n 叉树的先序遍历，不是二叉树。不要上来直接丢一坨二叉树先序遍历的代码。。这样会让人感觉你这个人办事不认真。。。
方法一：递归

var preorder = function(root) {
  const res = [];
  traverse(root);
  return res;

  function traverse(root) {
    if (!root) return root;
    res.push(root.val);
    let child = root.children;
    for (let i = 0, len = child.length; i < len; i++) {
      traverse(child[i]);
    }
  }
};

方法二：迭代

var preorder = function(root) {
    const res = [];
    if (!root) return res;
    const stack = [];
    stack.push(root);
    while (stack.length) {
      const node = stack.pop();
      res.push(node.val);
      for (let i = node.children.length - 1; i >=0; i--) {
        stack.push(node.children[i]);
      }
    }
    return res;
};

剑指Offer 32 - II.从上到下打印⼆叉树Ⅱ

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。



例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]


提示：

节点总数 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
这道题很简单，从题目我们就能看出考的就是二叉树的层序遍历，关于二叉树的层序遍历，前面已经讲过，这里就不再赘述了。

var levelOrder = function(root) {
  const res = [];
  if (!root) return res;
  const queue = [root];
  while (queue.length) {
    const level = [];
    for (let i = 0, len = queue.length; i < len; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(level);
  }
  return res;
};

⼆叉树的锯⻮形层序遍历-103

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：猛一看似乎不好下手，实际考察的还是二叉树的层序遍历。相比之前的二叉树的层序遍历只不过多了个方向控制而已，我们加个标志位控制方向即可。

var zigzagLevelOrder = function(root) {
  const res = [];
  if (!root) return res;
  const queue = [root];
  // flag 用于控制方向，true 表示从左向右遍历；false 表示从右向左遍历；
  let flag = true;
  while (queue.length) {
    const level = [];
    for (let i = 0, len = queue.length; i < len; i++) {
      const node = queue.shift();
      if (flag) {
        level.push(node.val);
      }else {
        level.unshift(node.val);
      }
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    flag = !flag;
    res.push(level);
  }
  return res;
};

二叉树的直径-543

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。



示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。



注意：两结点之间的路径长度是以它们之间边的数目表示。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/diameter-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var diameterOfBinaryTree = function(root) {
  let maxDiameter = 0
  maxDepth(root)
  return maxDiameter

  function maxDepth(root) {
    if (!root) return 0
    const leftMax = maxDepth(root.left)
    const rightMax = maxDepth(root.right)
    maxDiameter = Math.max(maxDiameter, leftMax + rightMax)
    return 1 + Math.max(leftMax, rightMax)
  }
};

var diameterOfBinaryTree = function (root) {
  let max = 0;
  var getMaxPath = (root) => {
    if (root === null) {
      return -1;
    }
    let left = root.left === null ? 0 : getMaxPath(root.left) + 1;
    let right = root.right === null ? 0 : getMaxPath(root.right) + 1;
    max = Math.max(max, left + right)
    return Math.max(left, right)
  }
  getMaxPath(root);
  return max
};

二叉树的最大深度-104

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。



来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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