共计 5951 个字符，预计需要花费 15 分钟才能阅读完成。
二叉树
下面的题目全都来自 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)
}
正文完
发表至： javascript
2020-07-01
