二叉树
下面的题目全都来自leetcode，直接leetcode搜名字可以找到。 属于比较常见的二叉树相关算法，难度：简单/中等
代码均为简单易于理解的版本，效率还不错
700. 二叉搜索树中的搜索
var searchBST = function(root, val) { if(root==null) return null; if(root.val==val) return root; if(root.val<val){ /////////这里不加return返回了undefined //外层函数无法收到返回值 return searchBST(root.right,val) }else { return searchBST(root.left,val) } };1564 二叉搜索树转链表
思路 二叉搜索树的中序遍历时做指针移动操作
var convertBiNode = function(root){ if(!root) return null let p=new TreeNode('head') //哨兵节点 let curr=p //始终指向最新的节点 var LDR=function(node){ if(!node) return null LDR(node.left) //指针移动 node.left=null //当前节点的左节点置空，不指向其他节点 curr.right=node //连接 curr=curr.right LDR(node.right) } LDR(root) return p.right }二叉搜索树与双向链表
剑指 Offer 36. 二叉搜索树与双向链表
//没有头节点的循环链表var treeToDoublyList = function(root) { if(!root) return let head=null p=head //p用于遍历 LDR(root) p.right=head //最后首尾的处理 head.left=p return head function LDR(node){ //放到外部传参的话不能改变p if(!node) return LDR(node.left) { if(p){ p.right=node }else{ //最左边节点 head=node } node.left=p p=node } LDR(node.right) }};平衡二叉树
var isBalanced = function(root) { if(judge(root)==-1) return false return true};function judge(root){ if(!root){ return 0 } let left=judge(root.left) if(left==-1) //该节点左孩子的左右子树不平衡，直接将该节点也返回不平衡 return -1 let right=judge(root.right) if(right==-1) return -1 if (Math.abs(left-right)>1) return -1 return Math.max(left,right)+1}102 二叉树层序遍历
关键：出队时左右孩子入队
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ var levelOrder=function(root){ let result=[]; if(root==null) return result; let queue=[root]; //根节点入队 while(queue.length>0){ let arr=[]; //////根据题目要求，每层的放在一个数组。因此还需一个循环控制 层 let len=queue.length; while(len){ //遍历当前层 let node=queue.shift(); //删除并返回首元素 arr.push(node.val); if(node.left) queue.push(node.left) if(node.right) queue.push(node.right) len--; ///**易漏 } result.push(arr); } return result; //每层放在一个数组中 }515. 在每个树行中找最大值
层序遍历时多了一步
var largestValues = function(root) { if(!root) return [] let res=[] let queue=[root] while(queue.length){ let len=queue.length let tmp=[] while(len){ let t=queue.shift() if(t.left) queue.push(t.left) if(t.right) queue.push(t.right) tmp.push(t.val) len-- } res.push(Math.max(...tmp)) } return res};1603 二叉树的镜像
///////////递归var mirrorTree = function(root) { let change=function(node){ if(!node){ return } //这里加入对子节点的判断能提高效率 //避免对子节点的两个null交换 if(node.left||node.right){ let temp=node.left //用[ ]解构交换更快 node.left=node.right node.right=temp change(node.left) change(node.right) } } change(root) return root};对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
//方法1. 递归var isSymmetric = function(root) { if(!root) return true let isEqual=function(left,right){ if(!left&&!right) return true //到底了,肯定为ture,否则中途会返回false if(!left||!right) return false //一空一不空 if(left.val!=right.val) return false //只剩值相等的情况，继续判断 return isEqual(left.left,right.right)&&isEqual(left.right,right.left) } return isEqual(root.left,root.right)};//方法2. 层序遍历var isSymmetric = (root) => { if (!root) return true let queue = [root.left, root.right] while (queue.length) { // 队列为空代表没有可入列的节点，遍历结束 let len = queue.length // 获取当前层的节点数 for (let i = 0; i < len; i += 2) { // 一次循环出列两个，所以每次+2*** let left = queue.shift() // 左右子树分别出列 let right = queue.shift() // 分别赋给left和right变量 if ((left && !right) || (!left && right)) return false // 不满足对称 if (left && right) { // 左右子树都存在 if (left.val !== right.val) return false // 左右子树的根节点值不同 queue.push(left.left, right.right) // 让左子树的left和右子树的right入列 queue.push(left.right, right.left) // 让左子树的right和右子树的left入列 } } } return true // 循环结束也没有遇到返回false}104. 二叉树的最大深度
var maxDepth = function(root) { if(!root) return 0 let right=maxDepth(root.right) let left=maxDepth(root.left) return Math.max(left,right)+1};111. 二叉树的最小深度
var minDepth = function(root) { if(!root) return 0; let left=minDepth(root.left); let right=minDepth(root.right); if(!root.left||!root.right) return left+right+1; return Math.min(left,right)+1; //左右均不为空};面试题34. 二叉树中和为某一值的路径
var pathSum = function(root, sum) { let res = [] let dfs=function(root, path, sum){ if(!root) return sum -= root.val if(sum == 0 && !root.left && !root.right){ res.push([...path, root.val]) return } path.push(root.val) dfs(root.left, path, sum) dfs(root.right, path, sum) path.pop()} dfs(root, [], sum) return res};两颗二叉树合并
都有节点时求和
var mergeTrees = function(t1, t2) { if(!t2) return t1 //t2空。t1是否空不重要 if(!t1) return t2 //t1空,t2不空 if(t1&&t2){ t1.val+=t2.val } t1.left=mergeTrees(t1.left,t2.left) t1.right=mergeTrees(t1.right,t2.right) return t1 //新树用t1返回};数组转二叉排序树（平衡二叉树）
var sortedArrayToBST = function(nums){ if(nums.length==0){ return null } let m=Math.floor((nums.length-1)/2) let p=new TreeNode(nums[m]) p.left=sortedArrayToBST(nums.slice(0,m)) p.right=sortedArrayToBST(nums.slice(m+1)) return p};二叉树公共祖先
（注意是二叉搜索树，容易确定在哪个子树上）
- 从根节点开始遍历树
- 如果节点p和节点q都在右子树上，那么以右孩子为根节点继续 1 的操作
- 如果节点p 和节点q都在左子树上，那么以左孩子为根节点继续 1 的操作
- 如果条件 2 和条件 3 都不成立，已经找到
临界条件：
- 根节点是空节点
- 根节点是q节点
- 根节点是p节点
从左右子树分别进行递归，即查找左右子树上是否有p节点或者q节点
- 左右子树均无p节点或q节点
- 左子树找到，右子树没有找到，返回左子树的查找结果
- 右子树找到，左子树没有找到，返回右子树的查找结果
- 左、右子树均能找到,说明此时的p节点和q节点在当前root节点两侧，返回root节点
var lowestCommonAncestor = function(root, p, q) { if(!root||root===p||root===q) return root; let left = lowestCommonAncestor(root.left,p,q); let right = lowestCommonAncestor(root.right,p,q); if(left&& right) //分别在root的左右两边 return root; return left!= null ? left : right; //都在左子树或都在右子树上};剑指 Offer 33. 二叉搜索树的后序遍历序列
//分治 每次判断左子树所有节点均小于当前根节点，右子树均大于当前根节点//var verifyPostorder = function (postorder){ let len=postorder.length if(len<3) return true //长度0，1，2时，一定能构造出来满足条件的树 root=postorder[len-1] //划分,找第一个比根节点大的 let i=0; for(;i<len-1;i++){ if(postorder[i]>root) break } //右子树是否满足 let flag=true for(let j=i+1;j<len;j++){ if(postorder[j]<root) flag = false } ////注意这里的区间 if(flag) return verifyPostorder(postorder.slice(0,i))&&verifyPostorder(postorder.slice(i,len-1)) (else) return false}剑指 Offer 07. 重建二叉树
var buildTree = function(preorder, inorder) { if(!preorder.length) return null //上个节点为叶节点，左右为null let node=new TreeNode(preorder[0]),i=0 for(;i<inorder.length;i++){ if(inorder[i]===node.val) break } node.left=buildTree(preorder.slice(1,1+i),inorder.slice(0,i)) node.right=buildTree(preorder.slice(1+i),inorder.slice(i+1)) return node};剑指 Offer 26. 树的子结构
题意：判断A是不是B的子树
var isSubStructure = function(A, B) { if(!A||!B) return false if(A.val===B.val&& find(A.left,B.left)&&find(A.right,B.right)) return true //根节点相同并且左右子树都相同（find递归） else{ return isSubStructure(A.left,B)||isSubStructure(A.right,B) }};let find=function(A,B){ if(!B) return true if(!A) return false if(A.val!==B.val){ return false } return find(A.left,B.left)&&find(A.right,B.right)}