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

遍历

递归

递归三部曲：
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);//左子树高度// 当判定左子树不为平衡二叉树时,即可直接返回-1if(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)=>{//到根节点且刚好和为targetSumif(targetSum===0&&!root.left&&!root.right) return true;// 遇到叶子节点而没有找到合适的边(计数不为0)，直接返回if (!root.left&&!root.right) return false;if(root.left){targetSum-=root.left.valif(backtracking(root.left,targetSum)) return true;targetSum+=root.left.val}if(root.right){targetSum-=root.right.valif(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;
};