广度优先遍历 — 队列先进先出
深度优先遍历 — 栈 先进后出

二叉树的数据结构

  1. function TreeNode(val, left, right) {
  2.       this.val = (val===undefined ? 0 : val) 
  3.       this.left = (left===undefined ? null : left) // 左子树
  4.       this.right = (right===undefined ? null : right) // 右子树
  5. }

求二叉树的最大深度

  1. var maxDepth = function(root) {
  2.     if(!root) {
  3.         return 0;
  4.     } else {
  5.         const left = maxDepth(root.left);//递归左子树
  6.         const right = maxDepth(root.right);//递归右子树
  7.         return Math.max(left, right) + 1;//1加左节点和有节点深度的较大者
  8.     }
  9. };

求二叉树的最小深度

  1. var minDepth1 = function(root) {
  2.     if(!root) return 0;  
  3.     if(!root.left && !root.right) return 1; // 到叶子节点 返回 
  4.     if(!root.left) return 1 + minDepth(root.right); // 只有右节点时 递归右节点  
  5.     if(!root.right) return 1 + minDepth(root.left); // 只有左节点时 递归左节点
  6.     return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
  7. };

求二叉树中节点的个数

  1. const getNodeSum=function(node){
  2.   if(node===null){
  3.     return 0;
  4.   }
  5.   let leftNum=getNodeSum(node.left);
  6.   let rightNum=getNodeSum(node.right);
  7.   return leftNum+rightNum+1;
  8. }

求二叉树中叶子节点的个数

  1. var findLeaves = function(root) {
  2.     let ans = []
  3.     const dfs = root => {
  4.         if(!root) return -1
  5.         let left = dfs(root.left), right = dfs(root.right)
  6.         let level = Math.max(left,right)+1
  7.         ans[level] = ans[level] || []
  8.         ans[level].push(root.val)
  9.         return level
  10.     }
  11.     dfs(root) // 深度优先搜索
  12.    // return ans;
  13. };

求二叉树中第K层节点的个数

判断二叉树是否是平衡二叉树

判断二叉树是否是完全二叉树

两个二叉树是否完全相同

两个二叉树是否互为镜像

翻转二叉树 VS 镜像二叉树


二叉树中插入节点