【数据结构】二叉树总结篇

遍历 递归

递归三部曲： 1.参数和返回值 2.终止条件 3.单层逻辑（遍历顺序）

var preorderTraversal = function(root) { // 第一种 let res=[]; const dfs=function(root){ if(root===null)return ; //先序遍历所以从父节点开始 res.push(root.val); //递归左子树 dfs(root.left); //递归右子树 dfs(root.right); } //只使用一个参数 使用闭包进行存储结果 dfs(root); return res; 迭代

借助栈或队列 前序和后序

前序遍历: // 入栈 右 -> 左 // 出栈 中 -> 左 -> 右 var preorderTraversal = function(root, res = []) { if(!root) return res; const stack = [root]; let cur = null; while(stack.length) { cur = stack.pop(); res.push(cur.val); cur.right && stack.push(cur.right); cur.left && stack.push(cur.left); } return res; }; // 入栈 左 -> 右 // 出栈 中 -> 右 -> 左 结果翻转 var postorderTraversal = function(root, res = []) { if (!root) return res; const stack = [root]; let cur = null; do { cur = stack.pop(); res.push(cur.val); cur.left && stack.push(cur.left); cur.right && stack.push(cur.right); } while(stack.length); return res.reverse(); };

中序

中序遍历: // 入栈 左 -> 右 // 出栈 左 -> 中 -> 右 var inorderTraversal = function(root, res = []) { const stack = []; let cur = root; while(stack.length || cur) { if(cur) { stack.push(cur); // 左 cur = cur.left; } else { // --> 弹出 中 cur = stack.pop(); res.push(cur.val); // 右 cur = cur.right; } }; return res; }; 层序

队列 当前层元素个数

var levelOrder = function(root) { //二叉树的层序遍历 let res = [], queue = []; queue.push(root); if(root === null) { return res; } while(queue.length !== 0) { // 记录当前层级节点数！！！ let length = queue.length; //存放每一层的节点！！！ let curLevel = []; for(let i = 0;i < length; i++) { let node = queue.shift(); curLevel.push(node.val); // 存放当前层下一层的节点 node.left && queue.push(node.left); node.right && queue.push(node.right); } //把每一层的结果放到结果数组 res.push(curLevel); } return res; }; 应用 反转二叉树

前序，若中序注意调整

var invertTree = function(root) { //1.前序 //递归 if(root==null)return null; //中,交换左右节点 swap(root) //左 invertTree(root.left); //右 invertTree(root.right); return root ; //中序遍历的话：左中右（右传的也是左指针，因为先翻完左树，再交换左右树，交换完的左数成右树了，所以还得传左！！！） //迭代法 if(!root)return null; let stack=[root]; while(stack.length>0){ let cur=stack.pop(); swap(cur) if(cur.left)stack.push(cur.left); if(cur.right)stack.push(cur.right); } return root; // //层次遍历（广度优先）->队列 if(!root)return null; let queue=[root]; while(queue.length>0){ let levelSize=queue.length; for(let i=0;i<levelSize;i++){ let cur=queue.shift(); swap(cur); if(cur.left)queue.push(cur.left); if(cur.right)queue.push(cur.right) } } return root; }; function swap(node){ left=node.left; node.left=node.right; node.right=left; } 对称二叉树

比较逻辑，后序遍历

var isSymmetric = function(root) { //比较节点 const compare=function(root1,root2){ //终止条件！！！,默认遇到底就返回true，所以只考虑那些为false的条件 if(!root1 && !root2)return true; else if(root1===null&&root2!==null||root2===null&&root1!==null)return false; else if(root1.val!==root2.val) return false //单层递归逻辑 let outside=compare(root1.left,root2.right); let inside=compare(root1.right,root2.left); return outside&&inside; } if(root === null) { return true; } return compare(root.left,root.right) }; 最大深度

后序 +1细节

var maxDepth = function(root) { //递归方法 if(root===null){ return 0 }else{ let left=maxDepth(root.left); let right=maxDepth(root.right); return Math.max(left,right)+1; } }; 最小深度

考虑左侧或右侧为空的情况，最小深度不是1而是另外计算算法

var minDepth = function(root) { //递归 //重点：递归终止条件 if(root===null)return 0; //叶子节点 // if(!root.left&&!root.right) return 1; if(root.left===null){ return minDepth(root.right)+1; } if(root.right===null){ return minDepth(root.left)+1; } let left=minDepth(root.left); let right=minDepth(root.right); let result=Math.min(left,right)+1; return result; } 完全二叉树的节点个数

普通二叉树解决

var countNodes = function(root) { //递归方法 const getNumbers=function(root){ //终止条件 if(!root)return 0; let left=getNumbers(root.left); let right=getNumbers(root.right); return left+right+1; } return getNumbers(root) }

利用完全二叉树性质+递归方法

//**终止条件 // if(!root)return 0; // //定义左右节点 // let left=root.left; // let right=root.right; // let leftDepth=0,rightDepth=0; // while(left){ // left=left.left; // leftDepth++; // } // while(right){ // right=right.right; // rightDepth++; // } // if(leftDepth===rightDepth){ // return Math.pow(2,leftDepth+1)-1; // } // return countNodes(root.left)+countNodes(root.right)+1; 平衡二叉树⭐

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1 -1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度

var isBalanced = function(root) { // //还是用递归三部曲 + 后序遍历 左右中 // //!!!当前左子树右子树高度相差大于1就返回-1,标识相差大于1的！！！！ const getDepth=function(node){ if(!node)return 0;//不为-1的所有数，用于标识 //确定单层遍历逻辑 let leftDepth=getDepth(node.left);//左子树高度 // 当判定左子树不为平衡二叉树时,即可直接返回-1 if(leftDepth===-1)return -1; let rightDepth=getDepth(node.right); if(rightDepth===-1)return -1; //判断左右子树高差 if(Math.abs(leftDepth-rightDepth>1)){ return -1; }else{ return 1 + Math.max(leftDepth,rightDepth); } } return !(getDepth(root)===-1) }; 二叉树的所有路径

回溯+递归算法 Javascript回溯算法大全——组合、分割、子集、排列和棋盘问题

回溯算法，就是将问题其抽象一棵树，而本次二叉树所有路径本身就是一棵树

var binaryTreePaths = function(root) { let res=[]; const backtracking=(root,value)=>{ //到叶子节点就返回 if(!root.left&&!root.right){ value+=root.val; res.push(value); return; } //前序,简单的回溯 value+=root.val+"->"; root.left&&backtracking(root.left,value); root.right&&backtracking(root.right,value) } backtracking(root,''); return res; }; 左叶子之和⭐

判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子： if(node.left !== null && node.left.left === null && node.left.right === null) 平时我们解二叉树的题目时，已经习惯了通过节点的左右孩子判断本节点的属性，而本题我们要通过节点的父节点判断本节点的属性。

后序遍历

var sumOfLeftLeaves = function(root) { //迭代 let sum=0; let stack=[root]; if(!root)return 0; while(stack.length){ let cur=stack.pop(); if(cur.left&&!cur.left.left&&!cur.left.right){ sum+=cur.left.val; } cur.left&&stack.push(cur.left); cur.right&&stack.push(cur.right); } return sum; } var sumOfLeftLeaves = function(root) { //采用后序遍历 递归遍历 // 1. 确定递归函数参数 const nodesSum = function(node) { // 2. 确定终止条件 if(!node) { return 0; } let leftValue = nodesSum(node.left); let rightValue = nodesSum(node.right); // 3. 单层递归逻辑 let midValue = 0; if(node.left && !node.left.left && !node.left.right) { midValue = node.left.val; } let sum = midValue + leftValue + rightValue; return sum; } return nodesSum(root); } 找树左下角的值 var findBottomLeftValue = function(root) { //Todo:最大深度，最左侧的值 // 层次遍历 let queue=[root]; if(!root)return null; let res; while(queue.length){ let length=queue.length; for(let i=0;i<length;i++){ let curNode=queue.shift(); if(i===0){ res=curNode.val; } curNode.left&&queue.push(curNode.left); curNode.right&&queue.push(curNode.right); } } return res; } 路径总和⭐⭐

回溯算法

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {boolean} */ var hasPathSum = function(root, targetSum) { //targetSum依次往下减，直至减到0且找到叶子节点，就找到路径 if(!root)return false; let backtracking=(root,targetSum)=>{ //到根节点且刚好和为targetSum if(targetSum===0&&!root.left&&!root.right) return true; // 遇到叶子节点而没有找到合适的边(计数不为0)，直接返回 if (!root.left&&!root.right) return false; if(root.left){ targetSum-=root.left.val if(backtracking(root.left,targetSum)) return true; targetSum+=root.left.val } if(root.right){ targetSum-=root.right.val if(backtracking(root.right,targetSum)) return true; targetSum+=root.right.val } return false; } return backtracking(root,targetSum-root.val); }; 路径总和II⭐⭐

处理根节点逻辑

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {number[][]} */ var pathSum = function(root, targetSum) { let res=[] if(!root)return res; let path=[root.val]; let backtracking=(root,sum)=>{ if(!root.left&&!root.right&&sum===targetSum){ res.push(path.slice()); return; } if(!root.left&&!root.right)return; //左 if(root.left){ path.push(root.left.val); sum+=root.left.val; backtracking(root.left,sum); sum-=root.left.val; path.pop(); } //右 if(root.right){ path.push(root.right.val); sum+=root.right.val; backtracking(root.right,sum); sum-=root.right.val; path.pop(); } return; } backtracking(root,root.val) return res; } 从中序与后序遍历序列构造二叉树

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {number[]} inorder * @param {number[]} postorder * @return {TreeNode} */ var buildTree = function(inorder, postorder) { //中序：左中右 //后序：左右中 //返回条件 if(!postorder.length)return null; //1.从后序找到中间节点 let midVal=postorder.pop(); let root=new TreeNode(midVal); //左中序，右后序 let index=inorder.indexOf(midVal);//找到中序的mid对应的索引 root.left=buildTree(inorder.slice(0,index),postorder.slice(0,index)); root.right=buildTree(inorder.slice(index+1),postorder.slice(index)); return root; }; 从前序与中序遍历序列构造二叉树 /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {number[]} preorder * @param {number[]} inorder * @return {TreeNode} */ var buildTree = function(preorder, inorder) { //前序：中左右 //中序：左中右 if(!preorder.length)return null; let midVal=preorder.shift(); let index=inorder.indexOf(midVal); let root=new TreeNode(midVal); root.left=buildTree(preorder.slice(0,index),inorder.slice(0,index)); root.right=buildTree(preorder.slice(index),inorder.slice(index+1)); return root; }; 最大二叉树

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {number[]} nums * @return {TreeNode} */ var constructMaximumBinaryTree = function(nums) { //构建二叉树类型题目——前序遍历 if(!nums.length)return null; //1.找最大 let max=-1,maxIndex=-1; for(let i=0;i<nums.length;i++){ if(nums[i]>max){ max=nums[i]; maxIndex=i; } } //2.构建根节点 let root =new TreeNode(max); //构建左边 root.left=constructMaximumBinaryTree(nums.slice(0,maxIndex)); //构建右边 root.right=constructMaximumBinaryTree(nums.slice(maxIndex+1)); return root; };