刷题技巧|二叉树刷题合集
二叉树解题的思维模式分两类：
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个traverse函数配合外部变量来实现，这叫「遍历」的思维模式。
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。
无论使用哪种思维模式，你都需要思考：
如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
543. 二叉树的直径
/**
* 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
* @return {number}
*/
var diameterOfBinaryTree = function(root) {
let maxnum=0;
findmax(root);//函数提升
function findmax(root){
if(!root) return 0;
let leftmax=findmax(root.left);
let rightmax=findmax(root.right);//后序遍历，求结点左右子树的最大深度之和即为直径
if(leftmax+rightmax>maxnum) maxnum=leftmax+rightmax;
return Math.max(leftmax,rightmax)+1;
}
return maxnum;
};
144. 二叉树的前序遍历
可以看到前面存在函数提升，下文中用到es6新语法const不存在变量提升，函数调用要在
/**
* 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
* @return {number[]}
*/
var preorderTraversal = function(root) {
let res=[];
const traver=(root)=>{
if(!root) return null;
res.push(root.val);
traver(root.left);
traver(root.right);
}
traver(root);
return res;
};
二叉树（纲领篇）ttps://mp.weixin.qq.com/s/nBPgZWPruZnuRiztMkblLg
226. 翻转二叉树
/**
* 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
* @return {TreeNode}
*/
var invertTree = function(root) {
const f=(root)=>{
if(!root) return null;
let temp=root.left;//左右结点交换即可，前后遍历顺序都可
root.left=root.right;
root.right=temp;
f(root.left);
f(root.right);
}
f(root);
return root;
};
102. 二叉树的层序遍历
/**
* 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
* @return {number[][]}
*/
var levelOrder = function(root) {
if(!root) return [];
let res=[];
let q=[];
q.push(root);
while(q.length){
let temp=[];//用temp保存每一层结点，再遍历所有结点的子节点
let t=[];
q.forEach((e)=>{
t.push(e.val);
if (e.left) temp.push(e.left);
if (e.right) temp.push(e.right);
})
q=temp;
res.push(t);
}
return res;
};
116. 填充每个节点的下一个右侧节点指针
/**
* // Definition for a Node.
* function Node(val, left, right, next) {
* this.val = val === undefined ? null : val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* this.next = next === undefined ? null : next;
* };
*/
/**
* @param {Node} root
* @return {Node}
*/
var connect = function(root) {
if(!root) return null;
const addr=(l,r)=>{//此函数的功能为将l的next指向r
if(l && r){
l.next=r;
//r.next=null; 不能这样写，会覆盖掉导致错误
addr(l.left,l.right);
addr(r.left,r.right);
addr(l.right,r.left);//两个空隙结点,左空隙指右空隙
}
}
addr(root.left,root.right);
return root;
};
114. 二叉树展开为链表
/**
* 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
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function(root) {
const flat=(root)=>{//定义函数功能为 将root为根的树拉平为链条
if(!root) return ;
flat(root.left);
flat(root.right);
//假设左右子树已经被拉平为一个链条
//后序遍历，从末尾开始将左子树最右结点接到左结点,即可保证每个子树都是扁平的
let leftnode=root.left;
let rightnode=root.right;//暂存右结点，最后添加到最底层结点的右结点
root.right=leftnode;//题目要求right指向下一节点，故换位置,将左子树作为右子树
root.left=null;
while(root.right!=null){//左结点已经移到右边,遍历到最底层结点，在最下面连接暂存的右结点
root=root.right;
}
root.right=rightnode;
}
flat(root);
};
二叉树（思维篇）https://mp.weixin.qq.com/s/odbfGvHdCT6YmPiRA2MT2g
559. N 叉树的最大深度
/**
* // Definition for a Node.
* function Node(val,children) {
* this.val = val;
* this.children = children;
* };
*/
/**
* @param {Node|null} root
* @return {number}
*/
var maxDepth = function(root) {
const find=(root)=>{
if(!root) return 0;
let maxdeep=0;
root.children.forEach((item)=>{
let childdeep=find(item);
maxdeep=Math.max(maxdeep,childdeep);
})
return maxdeep+1;
}
return find(root);
}
面试题 04.02. 最小高度树
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
const buildtree=(nums)=>{
if(nums.length===0) return null;
let mid=Math.floor(nums.length/2);
let root=new TreeNode(nums[mid]);
root.left=buildtree(nums.slice(0,mid));
root.right=buildtree(nums.slice(mid+1));
return root;
}
let root=buildtree(nums);
return root;
};
654. 最大二叉树
/**
* 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) {
const maxtree=(nums)=>{
if(nums.length===0) return null;
let max=0,index=0;
for(let i=0;i<nums.length;i++){//找到最大值和索引
if(nums[i]>max) {
max=nums[i];
index=i;
}
}
let leftnums=nums.slice(0,index);//划分数组
let rightnums=nums.slice(index+1,nums.length);
let root=new TreeNode(max);//构造根结点
root.left=maxtree(leftnums);//构建子树
root.right=maxtree(rightnums);
return root;
}
let root = maxtree(nums);
return root;
};
105. 从前序与中序遍历序列构造二叉树
/**
* 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) {
const build=(pre,ino)=>{
if(pre.length===0 || ino.length===0) return null;//判断终止条件
let rootnum=pre[0],index=0;//先序[0]即为根结点
for(let i=0;i<ino.length;i++){//找到中序数组中root的索引
if(rootnum===ino[i]) {
index=i;
}
}
//难点在划分前序数组的左右子树
let inleftnums=ino.slice(0,index);//划分中序数组
let inrightnums=ino.slice(index+1,ino.length);
let leftsize=inleftnums.length;//前序和中序的左子树长度一样
let preleftnums=pre.slice(1,1+leftsize);
let prerightnums=pre.slice(1+leftsize,pre.length);
let root=new TreeNode(rootnum);//构造根结点
root.left=build(preleftnums,inleftnums);//构建左子树
root.right=build(prerightnums,inrightnums); //构建右子树
return root;
}
let root = build(preorder,inorder);
return root;
};
1.前序遍历：根-左-右，中序遍历：左-根-右
2.对于preorder，每个首元素即为一个子树的根元素；对于inorder，需要查找preorder中根元素的所在位置mid
3.在inorder序列中，mid左边为当前根元素的左子树，mid右边为preorder当前根元素的右子树
4.在preorder序列中，因为mid即为左子树的个数，可截取到左右子树的序列出来
5.以此递归构造出一颗二叉树即可
简化版
var buildTree = function(preorder, inorder) {
if(!inorder.length) return null //判断终止条件
let temp = preorder[0], mid = inorder.indexOf(temp)//找根结点和索引位置
let root = new TreeNode(temp)
root.left = buildTree(preorder.slice(1,mid+1),inorder.slice(0,mid))//构建子树
root.right = buildTree(preorder.slice(mid+1),inorder.slice(mid + 1))
return root
};
106. 从中序与后序遍历序列构造二叉树
/**
* 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}
*/
1.后序遍历：左-右-根，中序遍历：左-根-右
2.对于postorder，末尾元素即为一个子树的根元素；对于inorder，需要查找preorder中根元素的所在位置mid
3.在inorder序列中，mid左边为当前根元素的左子树，mid右边为preorder当前根元素的右子树
4.在postorder序列中，因为mid即为左子树的个数，可截取到左右子树的序列出来
5.以此递归构造出一颗二叉树即可
var buildTree = function(inorder, postorder) {
if(inorder.length===0) return null;//判断终止条件
let rootnum=postorder[postorder.length-1];//根节点的值
let midindex=inorder.indexOf(rootnum); //索引值,也可看作左子树的长度
let root=new TreeNode(rootnum);
root.left=buildTree(inorder.slice(0,midindex),postorder.slice(0,midindex));
root.right=buildTree(inorder.slice(midindex+1),postorder.slice(midindex,postorder.length-1));
return root;
};
889. 根据前序和后序遍历构造二叉树
/**
* 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[]} postorder
* @return {TreeNode}
*/
思路都差不多，按照题目给出的列子去逐一判断左右子树的边界即可
var constructFromPrePost = function(preorder, postorder) {
if(postorder.length===0) return null;//判断终止条件
let rootnum=postorder[postorder.length-2];//右子树根节点的值
let midindex=preorder.indexOf(rootnum); //索引值
let root=new TreeNode(preorder[0]);
let leftsize=midindex-1;
//重点在下面判断左右子树边界 root.left=constructFromPrePost(preorder.slice(1,midindex),postorder.slice(0,leftsize));
root.right=constructFromPrePost(preorder.slice(midindex),postorder.slice(leftsize,postorder.length-1));
return root;
};
阅读剩余
版权声明：
作者：chun
链接：https://chun53.top/1251.html
文章版权归作者所有，未经允许请勿转载。
THE END