31道二叉树算法,给自己的五一礼物


前言

最近把树的算法做了一个小小滴总结。这些标题来自leetcode,都是一些代表二叉树算法思想的经典标题。

比方高度平衡二叉树二叉查找树BSTtire树等数据结构,深度广度优先遍历递归迭代等算法思想。假如关于递归不熟悉可以看看我的算法榜首篇《雾都孤儿》图文并茂,手刃算法,也可以谈论里留言,下一秒小巧就来回复各位兄弟姐妹的问题。

我也是一个算法渣渣,刚开端看着他人的解说都无法了解递归是什么意思,就像之前不明白之前倒车入库方向盘左打车为什么车往左面走相同(捂脸)。总之自己便是算法痴人。可是我想坚持下去必定会有成i R j – 7 ! 7 @果的,只是一个时刻的问题。

下面的标题其实自己我做了两到三I p u e遍才做到自己独立处理,共享出来一方面是想给在算法操练的掘友们一些参阅,一方面是也是对自己二叉树算法的一个概括总结吧(给自己的五一礼物)。

代码底子上都是javaScr( . N M F j b {ipt完成,由于重要的是思想而且代码不算杂乱,由于在最终一题里边用到了原型链的知识,因而最终一题我也用java写了一遍方便非& l * [ R H前端的掘友参阅。当然思路都是相同的。

树的底子概念

R Q X 1 & ~如你对树的结} 8 0 x # F 4 R R构纯熟于心那么就直接看看习题,敞开你的五一算法之旅吧~

概念介绍

  • 满二叉树:满二叉树便是每一个结点都有左子树和右子树,而且一切叶子结点都在同U y x一层。
  • 彻底二叉树:是满二叉树的子集。
  • 平衡二叉树:结点的左右子树高度差不超越1,后边的标题有呈现
  • 二叉查找树:二叉查找树的中序遍历有序,左孩子都小于根结点,右孩子都大于根节点
  • 前缀树:前缀树也叫J 8 n O h Y L 5 s字典树,来一个前缀树的图吧,来自百度百科

31道二叉树算法,给自己的五一礼物
每一个结点都或许有26个不同的子节点,结点值是a-z26个字母。


别的还有一些底子概念可以作为了解:

  • 结点的度:结点的度便是该结点射出的分支数,是横向的。射出的分支数是0那么结点的度便是0。
  • 树的度:结点度的最大值便是树的度。
  • 树的深度:结点层次最大值便是树的深度
  • 结点的层次:根V C G 8 t节点到这个结点的分支数条数,只要一个结点的数中,该结点的层次是0

x d x c ` b四个概念是相对的,假如分两类便是从横向和纵向进行区别。我简记为:“横度纵生”。这四个字的意思是结点的度那么便是代表横向;树的深(生)度便是代表纵向。

2.二叉树的性质

尽管下面的算法题很少用到,可是我觉得这作为底子素质是需求知道滴。

  • 性质1:非空二叉树的第i层上最多有2^i(榜首层咱们的i=0)S j t 9 q 6 v Z
  • 性质2:满二叉树的结点个数是2^(P w H $ + ~ xk+1)-1。k是结点层次存在第R 9 ? M , X0层。该定论可以依据等比数列核算。
  • 非空二y K X M叉树的叶节点$ P ) k树n0,度为2结点树为n2,那么存在联系n0=n2+1.依据分支射入和分支射出和总结点的联系可以判别出来。

3.二叉树的遍历

二叉树由三部分组成,根节点,左子树,右子树。依据根节点的拜访次第可以分为三种。即前序遍历,中序遍历,后续遍历。除了按结点类型遍历,还有同一层先按左子树再右子树遍历的层序遍历。

  • A c H X : T 6序遍历
    前序遍历先遍历根节点,再左子树,最终右子树。
  • 中序遍历
    中序遍历先遍历左子树,再根结点,再右子树。
  • 后续遍历
    后续遍? e u r o + _历先遍历左子树,在右子树,最终根结点。
  • ps:前序遍历和后续遍历不能确定一棵树。比方前序AB,后续BA,不知道树是ABnull还是AnulB
  • 层序遍历:层序遍历使用行列,先进先出思想。一层层遍历。根节点入行列– h J R,取出队首元素,假如有左节点和右结点就让左右节点入行列,再取出队首元素…直到行列为空。这样有点笼统T C # Y ~,后边咱们结合标题来看比方19题。

非递归完成遍历

借助仓库完成,仓库有先进后出的特点。非递归完成二叉树的前序I E W $ t o O遍历先让根节点入栈,取出根节点元素,假如左子树非空就让左子树入栈,然后弹出栈顶元素,看该元素是否有右节点,假如E ) c # o g V有右节点入栈,E H x s p 8 r } %再弹出栈顶元G 9 K H素直到栈为空。后边也会有相关的标题例如12题。

leetcode原题

树的底子性质

1 & I + ) Y首题:树的最大高度-104

  • 标题:给一棵树回来树的最大高度,也便是树的深度。如下:
Given binary tree [3,92 u U X q,20,null,1 W [ d $ r . T (nul* C yl,15,7],
3
/ 
9  20
/  
15   7l % W g 2 7 R /
return its depth = 3.
  • 剖析:
    求树的高度咱们可以找出左子树的高度和右子树的高度,两者较大的值+1便是当时树的高度。f o T X左子树的高度可以用左左子树的高度u y 8 5 W 8 v 6和右右子树的高度中的较大值+1求解。咱们就找到了递归的规律,什么时分回来呢?也便是什么状况下是出: x V M口,当遍历到结点为空的时分就递归到了最终一层。所以root==null便是出口了。

  • 解题

varP A p s maxDepth = function(root) {
if(rooth I D 5==null) r, k R Yeturn 0;
return Math.max(maxDepth(root.left),  maxDepth(root.right) )+1;
};

第二题-平衡树1r = ` e }10

  • 标题:给你一棵树判别是否是平衡二叉树
Given a binary tree, det! ] z = Q c %ermineC V 5 ! S & c 3 if it is height-balanced.
Given the following tree [3,9,20,null,null,15,7]:
3
/ 
9  20
/  
15   7

平衡二叉树便是结点的左右子树的高度差<=1

  • 剖析:
    与前面的类似,递归找到左右子树的高度,然后左右子树高度差假如大于1就回来false,否则为true。所以咱们需求知道当时结点左右子树的高度差<=1&&当时结点的左孩子的左右子树高度差<=1&&当时结点的右孩子4 ) 9 z n }的左右子树高度差<=1。当着三个Z | B条件都满意的时分时分便是true.
  • 解题:depth函数求左右子树的高度。
var isBalanced = function(root) {
if(root==null) return true;
var cuu A @ yr= Math.abs(depth(root.left)-depth(root.right))>1? false : true;
return cur&&Q ~ 0 W ) { N D Lamp;isBalanced(root.left) &&ap w I 0 ! Mmp; isBalanced(root.rigS q D # j P Tht);
}
function depth(root) {
if(root ==null) return 0;
var l = depth(e ` + : ] U ? 9 vroot.left);
var r = depth(rootN + # p # 6 N.right);
return Math.max(l,r)+1
}

第三题-翻转树2t % # C 826

  • 标题:
翻转一棵二叉树。
示例:
输入:
4
/   
2     7
/    / 
1   3 6   9
输出:
4
/   
7     2
/    / 
9   6 3   1

力扣(LeetCode)

  • 剖析:也可以用递归完成,e 6 N交流左子树翻转的成果和右p X O ( t k 6子树翻转的成果。左子树翻转的成果是左左子树和右右子翻转的成果进行交流得到…直到最终一个结点的左右子树为空回来。
  • 解题F 3 0 ( F * * X /E 8 g r E
var invertTree = function(root) {
ia ` qf(!root) return null;
//左子树是左子树回转后的成果
root.left = invertTree(root.left);
//右子树是右子树翻转的成果& 6 U
root.right = invertTree(root.right);
var temp = root.left;
root.left = root.right;
root.right = temp;
return root[ 3 G;
};

第四题-归并两棵树617

  • 标题:
给定两个二叉树,想象当你将它们中的一个l & g | V覆盖到另一个上时,两个二叉树的一些节点便会堆N ( b叠。
你需求将他们兼并为一个新的二叉树。兼并的规则是假如两个节点堆叠,那么将他们的值相加作为节点兼并后的新值a R ` W e z l,否则不为NULL 的节点将直接作为新二叉树的节点。
输入:
Tree 1                     Tree 2
1                         2
/                        / 
3   2                     1   3
/                              
5                             4   7
输出:
兼并后的树:
3
/ 
4   5
/    
5   4   7 I R a q E

力扣(LeetCode)

  • 解析Z P ? G:二O / a : * v [叉树兼并可以看做是一个树的结点值加上别的一棵树的结点值。运用递归。当时结点值相加+左子树兼并的成果+右子树兼并的成果便是最终要回来R / @ t d = b x 3的树。左子树兼并的成果=左孩子当时结点值+左左子树兼并的. ; f成果+右右子树兼并的成果。直到两棵树上的结点都遍历完就回来。
  • y i g 4 ,题:
var mergeTrees =s E L s S K W function(t1, t2) {
//假如左右子树都空
if(!t1&am+ % v f ~ / M Np;&!t2) return null;? T | Q 2 . g
//假如左右子树有一个空
if(!t1||!t2) return t1||t2;
t1.val = t1.val+t2Y f [ X 9 $ S.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
};

二叉树途径问题

第五题-树的最长途径543

  • 标题:
给定一棵二叉树,你需u P C G U W s -求核算它的直径长度。一棵二叉树的直径长度是恣意两个结点途径长度中的最大值。这条途径或许穿过也或许不穿过根结点。
示? ; _ ~例 :
给定二叉树
1
/ 
2   3
/ 
4   5
回来3, 它的长度是途径 [4,2,1,3$ | i l ! j D] 或许[5,2,1,3]。
留意:两结点之间的途径长度是以5 , ] * o [ 2 ` /它们之间边的数目表明。

D q 9扣(LeetCode)

  • 剖析:这道题咱们要知道树的直径便是一棵树一个结点到别的一个结点的最大值。标题的比方中很简单让咱们误解为最大长度便是左子树的高度+右子树的高度。可是不完满是这样的,咱们遍历每个结点的时分要记载当时直径的最大值,然后判别下一个结点的最大值和当时最大值的巨细,假如下一个结点的直径最大值大于当时} ? V $ ^ F G P最大值,那么就L ? ^ ~要更新最大值。

比方下面的比方中:值为-5的结点的直径是7,根节点-9的直径是6。所以直径o q C 最大值不必定是左子树深度和右子树深度和

31道二叉树算法,给自己的五一礼物
  • 解题
var diameterOfBinaryTree = function(root) {S w T 9 a u s
if(!root) return 0;
var max = 0;
function maxdepth(ro) _ 4 7 N Bot){
if(!root) ret* R J z 8 x } 2urn 0;
var left = maxdepth(root.left);
varz a ! B % O right = maxdepth(root.right);
//更新直径的最大值
max = Math.max((left+ right),max);
return Math.max(left, right)+1
}
maxdepth(root);
return8 ! ? ; 6 : Y S max;
}

时刻杂乱度为O(n):遍历结点的数d Y N / ( s u

空间杂乱度O(height):树的高度

第六题-判别途径和是否等于一个数112

  • 标题:
给定一个二叉树和一个方针和,判别该树中是否存在根节点到叶子节点, * ) P [的途径,这条途径上一切节点值相加等于方针和。
阐明:g _ 9 9叶子节G T u L 5 1 k &点是指没有子节点的节点。
示例:
给定如下二叉r n  } X 7 @ ^ .树,以及方针和 sum = 22,
5
/ 
4   8
/   / 
11  13] S W P  4
/        
7    2      1
回来 true, 由于存在方针和为 22 的根节点到叶子节点的途径 5-&g8 $ T O ht;4->11->2。

力扣(LeetCode)

  • 解析:遍历树结点。当遍历完且遍历的一切结G { L { : # g k点和1 S J 9 J h S $等于sum就回来true
  • 解题:
<!--//过错的办法,不满意全局性:左子树假如不满意遍历完回来false不会遍历右子树-->
<!--var hasPathSum = function(root, sum) {-->
<!--    iv ( 4 r ;f(!r: Z Ooot)return false;-->
<!--    if(root.val == sum&& roW & q X Z Sot.left==null&&roob u :t.right==null) return true;-->* F - ( X 1;
<!--    // return hasPathSuz 7 1 A G R zm(root.left, sum-roo= 5 :t.val)||hasPathSum(X P 1 a 2 = Sroot.right,sum-root.val);--&g* w 5 * v ? /t;
<!--    if(!roo.left)hasPathSum(root.left, sum-root.val);-->
<!--    ifD K 0 | 7(!ra o = ioot.right)hasPathSum(root.right,sum-root.val);-->
<!--};--&g) { q b : ^ k ot;
//正确的回答
var hasPathSum = function(roL F s J /ot, sum) {
if(!root) return false;
if(root.val == sum&&D x -; root.left==null&aT Q 8 l j * mp;&root.right==null) return true;
return hasPathSl W M *um(root.left, sum-root.val)||h/ % ^asPathSum(root.right,sum-root.val);
};

第七题-核算一棵树满意要求的途径数量437– ] H 9 ^ , c ]

  • 标题:
给定一个二叉树,它的每个结点都存放着一个整数值。
找出途径和等于给定数值的途径总数。
途N c # } Y  - j $径不需求从根节点开端,也不需求在叶子节点完毕,可是途径方向有必要是向下的(只能从父节点到子节点)。
二叉树不超越1000个节点,且节点数值范围是 [-1000000,1000000] 的E A ! C y 5整数。
示例:
root = [10,5,-3,3E Q M * [ ; M & z,2,nullG K j n ? L,11,3,-2,null,1], sum = 8
10
/  
5   -3
/     
3   2   11
/    
3  -2   1
回来 3。和等于 8 的e e Y H z途径有:K b f = v
1.  5 -> 3
2.  5 -> 2 -> 1@ * d
3.  -3 -> 11

力扣(LeetCode)

  • 解析:核心也是树的深度优先遍历,可是这个遍历纷歧样,一条途径就可以从恣意结点开端,所以说每一个结点都是根结点。拿上面的比方来看咱们把10作为根结点遍历没有找到一条满意要求的,然后就把5作为根结点遍历找到了两条满意要求的途径,然后把3作为根结点来看有没有满意要求的….

    那么怎么看是否满意要求呢,便是当时的结点值valu; 2 8 n O F Te是否和sum持平,假如持平就找到了一组,然后持续遍历找到以根结点开端一切满意标题要求的途径。这D p u H %也是一个递归,递归– D X B 1的等式是满意要求的途径数count=根结点root是否满意value==sum&&root.left是否满意value == sum-root.value&&root.right 是否满意value==sum-root.leftz 3 e。对应于path函数。

  • 解题:

//两层递归
varS a d 2  pathSum = functioW { {n(ro/ t o fot, sum) {
if(!root) return 0;
function pa- R - 2 u  9th(root, sum) {
var count = 0;
if(!root) return 0;
if(root && root.val == sum) count++;
count += path(root.left, sum-root.val)+path(root.right, sum-root.val);
return count;
}
return  path(root, sum)+pathSum(root.left, sum)+pathSumJ - C o(root.right, sum);
};

第八题-最小途径111

  • 标题
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短途径上的节点数量。
阐明:叶子节点是指没有子节点的节点。
示例:
给定二叉树[3,9,20,null,null,15,7],
3
/ 
9  20
/  
15   7
回来它的最小深度 2.

力扣(LeetCode)

  • 剖析:这 [ 8 F L P ` p个标题或/ H g O ;许榜首感觉和104求最大深度相同,假如是这样那么[1,2– N | ~ 6 }]就不满意了,所以当左右子树其间有一个为零的时分要取非0值再加1B D N $ s @ S.
  • 代码完成
var minDepth = function(root) {
if(!root) return 0;
let l = minDepth(root.leM } * r f D Sft);
let r= minDepth(root.right);
//取左或右子树有一个为0的时分取非0的值
if(l==0&C G e * W k &r!=0||r3 ; l t s L==0&&l!=0) return (l||r)+1;
return Math.min(l, r)+1;
};
  • 时刻杂乱– F 2 n c , Q 9度:咱们拜访每个节点一次,时刻杂乱度为 O(N)O(N) ,其间 NN 是节点个数。
  • 空间杂乱度:最坏状况下,整棵树是非平衡的,例如每个节点都只要一个孩子,递归会调用 N(树的高度)次,因而栈的空间开支是 O(N) 。但在最好状况下,树是彻底平衡的,高度只要 log(N),因而在这种R # `状况下空间杂乱度只要O(log(N)) 。
办法二

选用层+ ) 5 e次遍历加两层循环,不用遍历完每一个结点。当当时结点是叶子结点的时分就回来当时结点的层数。

var minDepth = functi% o - p l A c Ion(root) {
if(!root) return 0;
if(!root.left&&!root.right) return 1;
let quene = [];//行列
let level = 0;
quene.push(r` } e a o b $oot);
while(quene.length/ ^ ? / |){
let size = quene.length
while(size--){
let cur = quen1 P j * Ke.shift();
if(cur.left!=null){
quene.push(cur.left);
}
if(cur.right!=null) {
quene.push(cuL v hr.right);
}
//找到叶子结点
if(!cur.left&&!cur.right){
return level+1;
}
}
level++;
}
};

第九题-124核算最大途径和(hard)

  • 标题
给定一个非空二叉树,回来其最大途径和。
本题中,途径被界说为一条从树中恣意节点动身,到达恣意节点的序列。该途径至少包含一个节点,且不必定经过根节点。
示例 1:
输入: [1,2,3]
1
/ 
2   3
输出: 6
示例2:
输入: [-10,9,20,null,null,15,7]
  -10
 / 
 9 20
  / 
 15  7
输? A h出: 42

力扣(Ley m c 7etCode)

  • 解析:这个标题要弄清楚途径和是什么意思,不是途径的条数,而是经过结点的vL ; Z W jalue相加的最大者,弄懂标题的意思后和543,687相同的道理。或许更严谨的是途径和有必要不小2 I ; G C , 于0,树最大途径和或许会呈现负值的状况(当结点的value是负)
  • 解题
var maxPathSum = funct^ m k j Zion(root) {
let max = Number.MIN_SAFE_INTEGER;;
cA { !onst path = (root) => {
if(root == null) return 0;
let left = Math.max(0,path(root.left));
let right =Math.max(0,path(root.right));
max = Math.max(max, left+right+root.val);
// reK L 2 Uturn left+right+root.val;不满意N Q k测验T B U二
return Math.max(left,rigg g ) 1ht)+root.val;
}
path(root);
return max;
};

第十题-相同结点值的最D 8 6大途径长度687

给定一个二叉树,找到最长的途径,这个途径中的每个节点具有相同值。 这条途径可以经过也可以不经过根节点。
留意:两个节点之K L Z间的途径长度由它们之间X ) y 8 o的边数表明。
示例 1:
输入N ` I =:
5
/ 
4   5
/    
1   1   5
输出:
2
示例 2:
输入:
1
/ 
4   5
/    
4   4   5
输出:
2
留意: 给定的二叉树不超越10000个结点。树的高度不超越1000。

来历:力扣(LeetCode)

  • 解析:这个标题最开端想的是两层递归遍历,把每一个结点作为根结点。然后记载当时的最大值然后s } C ~比较更新最大值。这个题有点像最大途径数,也便是leetcode543.与之不同的是多了连个参数leftpath和rightpath来记载相同值的结点,回来值也纷歧样,可是大致思路相同。
  • 解题
var longestUnivaluePath = function(root) {
// //当时树的途径数
if(!root)J R d o b P - j returv } @ ln 0;
let max = 0;
const depth = (root)=>{
if(!root) return 0;
let left = depth(root.left);
let right = depth(root.right);
let leftpath = (rH ) ; ] Z Z {oor z .t.left&&root.left.val==root.val)? left+1X E Q:0;
let rightpath = (root.right&&root.right.val==root.val)? right+1:0;
max = Math.max(max, leftpath+rightpath);
return Math.max(leftpath,rightpath)
}
depth(root);
retur# s V zn max;
};
《----------M ^ %-------D v } + Z t-----------------------------------------------》
与之类似的还有129求途径的结点和,中[ z c X ! d b t等难度
var sumNumbers = funR K s # p +ction(root) {
let sum = 0;
let cur = 0;
if(!root) return 0;
const path = (C T q rroot,cur)=>{
cur = cur*10 + root.val;
//叶子结点回来当时
//根节点的值加左子树数字和加右子树数字和
if(root.left) path(root.left, cur);
if(rooF M T ct.righW G ( zt) path(rooT g $ R ) S h qt.right, cur);
//叶子结点的时分和为cur
if(!roo| ; X Kt.l8 P c keft&&!root.right) sum += cur;
}
path(root,0);
return sum;
};

第十一题-子树572

  • 标题:这个题与第七题-437解法类似,也是两层# 5 r B ] O @递归,因而将它放在这。
给定两个非空二叉树 s 和 t,查验s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包含 s 的一个节点和这个节点的一切子孙。s 也可以看做它本身的| 7 E一棵子树。
示例 1:
给定的树 s:
3/ g p ^ 
/ 
4   5
/ 
1   2
给定的树D b J , t:
4
/ 
1   2
回来 true,由于 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s:
3
/ 
4   5
/ 
1   2
/
给定的树 t:
4
/ 
1   2
回来 false。

力扣(LeetCU 8 x 7 L , dode)

  • 解析:和上面一题很像,两层递归。榜首层递归y r h 3 b是遍历每个结点,把s每个结点作为根结点,然后第二层递归判别两X X [ c z M F l h棵树是否相同。相同是树是根结点到叶子结点都相同。比方标题中第二个比方回来false由于叶子结点不同。
  • 代码
var isSubtree = function(s, t) {
if(!s) return false;
//判别两棵树是否相同
let judege = function(s, t) {
if(!s&&!t) return true9 t C;
if(!s||!t) return false;
if(s.val != t.val){
reW e = N Uturn false;
}
return j| a m 1 7 H O Yudege(s.leftn V ~ 6 M ;,t2 g 3.left)&&judege(s.right, t.right);
}
//三者只要一个建立即可
ret;  k f Murn judege(s,t)|| isSubtree(s.G L Zleft, tV t 4 - p T x V)|| isU P z 4 . b d ! %Subtree(s.right, t)
};

二叉树遍历

第十二题-非递归完成二叉树前序遍历144

  • 标题
给定一个二叉树,回来它的前序遍历。
示例:
输入: [1J Q [ ( H @,null,26 j ` - - X,3]
1

2
/
3
输出: [1,2,t n X D { W {3]
进阶:递归算法很简单,你可以经过迭代算法完成吗?

:力扣(LeetCode)

  • 解析:前序遍历,遍历根结点,再遍历左子g H h 6树,再遍历右r 9 _ c m子树。这h ( z . T I 8 @ 0儿写一下迭代算法,也便是使用栈非递归完成二叉树的遍历
  • 回答
var preorderTraversal = function(root) {
let result = [];
if(!root) return result;
//递归
// const helper = (root) => {
//     if(rootn 3  x P T D R x) result.push(root.val);
//     if(r% ~ C 8 H J O Yoot.left) helper(root.; 5 c q Fleft);
//     if(root.+ G 1 V (right) helper(root.right);
// }
// helper(root);
// return result;
//迭C 4 v W , K u代
let stF @ 1 S ack = [root];
while(stack.length!=0){
let node = stack.w P opop()d ^ k;
reB ; E m N +sult.push(node.val);
if(node.right) stack.pusw s E 0 | N u o Zh(node.right);
if(node.left) stacT r 5 f 6 b j 0 Lk.push(node.left);
}
return reH r % - / F 6 ` .sult;
};

第十三题-非递归完成二叉树的后续遍历145(hard)

  • 标题
给定一个二叉树,回来它的 后序遍历
示例:
输入: [1,null,2,3]
1

2
/
3
输出: [3,2,1]

力扣9 p J 6 C : Q *(LeetCode)

  • 解析:与上面的办法类似,可以递归先序遍历然后逆序输出。也可以迭代每次更新栈顶元素得到先序遍历成果再逆序输出。值得留意的是` X ! C W $ : 7 i后序遍历左孩子,右孩子,根结Y 1 1 * k ! :点,。那么先序的次序是根节点,右孩子,左孩子r { ` 9 9 ` + B I而不是根节点,左孩子,右孩子
  • 代码
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
//先序遍历逆序后便是后序遍历
let result = [];
if(t . 4 1 ^ M ]!root) re# B } . E 4 E a 8tur[ % 6 = q Cn result;
// const helper = (root) => {
//     if(root) resuo R h 5 d ~lt.push(root.val);
//     if(root.riC X E J M 2 dght) helper(root.right);
//     if(root.left) helper(root.left);
// }
// helper(root);
// return result.reverse();X r 3 K w % s
let stack = [root# ( 8 e H];
while(stack.length){
let len = stack; % z 0 ~ ^ #.lengths  o C 6 b e i Y;
while(len--){
let node = stack.pop();
result.push(node.val)
if(node.left) stack.push(noh 1 m O M i  ; pde.left);
if(Z @ , Anode.right) stack.push(node.right);
}
}
return result.reverse();
};

第十四题-非递归完成二叉树的中序遍历94(中等)

  • 标题
给定一个二叉树,回来它的中序遍历。
示例:
输入: [1,null,2,3]
1

2
/
3
输出: [1,3,2]

力扣(LeetCode)

  • 思想:尽管这个标题是中等难度,可是我认为中序遍历是三者难度系数较大的。经过nod9 V qe指针先将根节点的左子树全部入栈,取出栈顶元素并将结点值保存到成果中。假如取出的栈顶元素有右子树就让右子树按序入栈再取出栈顶元素。比较难了解的两个点在代码里边都有注释
  • 代码
var inorderTraveW M p /  3 e / !rsal = function(root) {
let result = [];
if(!root) return result;
let stack = [root];
let node =* X r I & M root.o Y G [ ~  ;left;
//增加node存在是处理根节点没有左子树的状况。没有左子树stack.length=c ~ x0的时分海[ Q 6 m / L *  b曙要将右子树入栈
whi* A n v 4le(stack.lenH j _ l ygth || node) {
while(node) {
//结x L h q x } 2 y点入栈
stack.push(node);
node =y r i T / node.left
}
node = stack.C k k % T $ ,pop();
result.push(node.val);
node = n% d ] d 6 e Lode.right;//node.rightG [ 1 c X存在就将node.r/ 3 @ R ? wight这个树的左节点入栈
}
return result;
};

第十五题-树的对称101

  • 标题
给定一个二叉树,查看它是否是镜像对称V 6 X的。
例如,二叉树[1,2,2,3,4,4,3] 是对称的。
1
/ 
2   2
/  / 
3  4 4  3
可是下面这个[1,2,2,null,3,null4 . E i r,3] 则不是镜像对o D - x x称的:
1
/ 
2   2
   
3    3
进阶:你可以运用递H P f 6归和迭代两种办法处理这个c B M B W  V问题吗?

力扣(} * 1 + ( d J _LeetCode

  • 解析:首要咱们递归完成,假如树是对称的那么左子树和右子树对称,右子树和左子树对称。镜像对称=左子树的榜首个孩子的value和右子树榜首个孩子的o h S * %value持平+左左子树和右右子树对称+右右子树和左左子树对称
  • 代码
//递归
var isSymmetric = function(root) {
if(!r` v ! u e i 9oot) reE @ H ; zturn true;
let same = functi* Q c d (on(root1, root2) {
//遍历到最终还没有false而且结点v $ - 4 H ` w e 9空
if(!root1 L M&&!root2) return true;
//恣意一个是空或许两个结点的value不等。
if(!root1|? - o B ! . F|!root2||root1.val != root2.val) return false;
return same(root1.left,root2.right)&&same(root1.right, root2.o - dleft)P S j 2 i;
}
return same(root.left,root.rig2 a 7 D J !ht);
};

当然还有迭代法使用行列,每次取行列队首的两个元素,然后比较值是否持平。假如两节点为空进行下一轮循环,假如一个空或许两者val不等就false,由于行列先进先出入队的四个结点的次序要留意一下。

//非递归
var iB ! - [ 4 QsSymmetric = function(root) {
//非递归完成
let qP ; G x u Y h S Iuene = [];
if(root.left.val!=root.right.val) return falsej p v o N;
qu. ? p p (ene.push(root.left);
quene.push(root.right);
while(quene.length){
let left = quene.shift();
let right = quw ? `ene.shq { L % } Uift();
// if(left.left!=right.right||left.right!=right.left) return false;逻辑过错
if(!left&&!right) continue;
if(!left||!right || left.val != right.val) reS o c A M H u  .turn false;
//入行列
if(left.left) quene.push(left.left);
if(right.r/ , sight) quene.push(right.right);
if(left.K T w Vright)4 A P quene.push(left.right);
ib M q . Nf(right.left) quene.push(right.left);
}
return true;
};

第十六题-核^ : a ) k + ` I q算左叶子结点的和404

  • 标题
核算给定二叉树的一切左叶子之和。
示例:
3
/ 
9  20
/  
15   7
在这个二叉树中,有两个左叶子,分别是 9 和 15,所以回来 24

8 ` y扣(LeetCode)

  • 解析:递归完成,假如左子树是叶子结点那就回来左子树的值加对右子树处理的成果。假如左子树不是叶子结点就回来对左子树和右子树处理的成果,怎么判别左子树是不是叶子结点的条件有三个,一个是该结点存在,二是该结点无左孩子,三是该结点没有右孩子。
  • 代码
var sumOfLeftLeaves = f^ z Y R n @ ] Vunction(root) {
if(root==null) return 0;
if(root.left&&!root.left.lp A r ~ K c ^ _eft&amW 0 `p;&!rootN 4 V Q # B.lef y z 7t.right)D v U , N  T | return root.left.val+sumOfLeftLeaves(root.rightl f M m m);
else return sumOfLeftLeaves(root.left)+sumOfg ] @ i { ? ` c fLeftL[ W 7 v ( 1eaves(root.right);
};

第十七题-距离遍历(打家劫舍2-好题)3+ I # D v K M s z37

  • 标题
聪明的小偷意识到“这个当地的一切房子的排列类似于$ g W _ J C一棵二叉树”。 假如两个直接相连的房子在同一天晚上被打劫,房子将主动报警。
核算在不触动警报的状况下,小偷一晚可以盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ 
2   3
   
3   1
输出: 7
解说:小偷一晚可以盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,1 l l . h ^ ! Pnull,1]
    3
/ 
4   5
/    
1   3   1
输出: 9
解说:小偷一晚可以盗取的最高金额= 4 + 5 = 9.

力扣(L8 s %eetCode)

  • 解析:这儿运用递归的办法遍历树,动态规划放到动态规划的专栏去解说。这个题可以了解为二叉树距离结点值的和最大@ E ( ! u t m f是多少。所以有两种状况,榜首种将root作为当时最大值,那么root的left和right不能算进去。总的最大值便是root+root.left.left+r- N l n U A , r !oot.left.right+root.right.left+root.right.right的结点和。

    第二种状况便是root不算进去,将root.left+root.righO J N p s N . + 2t的结点和作为最大值。
    最终的最大值应该是榜首种和第j 1 r j [二种的最大值。关于递归的出口便是当结点不存在回来0.

  • 回答:k ! u ?

var rob = fun: 9 ( Rction(root) {
if(!root) return 0;
let result1 =root.val ;
//榜首种
if(root.left)result1 += rob(roQ P i , 0 ? , 0ot.l, k eeft.lP ` & * w .eft) + rob(root.left.right);
if(root.right) result1 +=rob(root.rightM ! . z m.left)+ rob(root.right.right);
//第二种
let result2 = rob(root.left) + rob(root.right);
return Math.max(result1, resulV K ? ; U ] 8 t $t2);
};
  • 弥补:g S 5 ; (这个标题我开端递归也没有想出来,感觉自己太菜了,休息一会发现自己想到啦,遍历当时结点,找出当时两种状况的最大值,当时状况最大值也是两种状况。找出他们的最大值。最终成果是result1和result2比照的成果。resul2成果resul b E ` #t2 = rob(root.left) + rob(root.right);rob(root.left)的成果是root.left作为根节点两种状况比照的成果。rob(roo8 d Ot.right)是root.right作为根节点两种成果比照后的成果。

第十八题-找出二叉树中第二小的结点671

  • 标题
给定一个非空特别的二叉树,每个节点都是正数,而且每个节点的子节点数量只能为2或0。假如一个节点有两个子节点的话,那么这个节点的值不大于它的子节点的值。
给出这样的一个二叉树,你需求输出一切节点中的第二D @ A G小的值。假如第二小的值不存在的话,输出 -1 。
示例 1:
输入:
2
/ 
2   5
/ 
5   7
输出: 5
阐明: 最小的值是 2 ,第二小的值是 5 。
示例 2:/ j Z 9
输入:
2
/ 
2   2
输出: -1
阐明:G f M J n K _ 最小的值是 2, 可是不存在第二小的值。

力扣(LeetCode9 O z . ) m F

  • 思路:开端认为第二小值必定在根节点的榜j J & E首个左孩子和右孩子之中,所以有了过错的解法v & t b。可是依据报错信息知道第二小值或许呈现在子树的任何– @ , ; u b s N一个方位(当孩子结点值与根节点相同的时分),因而要进行递归。

    • 第二小值不或许是根节点,所以找左右n x * %子树的较小者作为第二小值
    • 当left.val==root.vm F $ % _ 9 o Cal的时分,要找到左子树的第二小值作为left的值。同理right.val==root.val的时分要找到右子树第二小值作为rig2 K Z T fht值。
    • 然后比较right和left哪个大。
  • 过错思路
//过错的思路:考虑不周部分测验用例经过,比方[1,1@ z q C I  ~ H,3,11,34,3,1,1,y Y E * ] 61,P U 9 + `3,8,4,8,3,3,1,2]这棵树就不建立。
//有0或2个叶子结点。
var findSecondMinimumValue = function(root) {
//没有结点
if(!root) return -1;
//只要一个根节点
if(!root.left&&!root.right) return -1;
//有一个叶子结点
if(!root.2 d U } c U )left||!root.right) return (root.left.val||root.right.vW ? } 6al)> root.val?(root.B O o F f Uleft.val||root.right.R x c ( .val):-1;
//有两个叶子结点找到两个叶子结点的小者
if(root.left.vc 2 - |al ==root.val&&root.right.val == root.val) return -1;
if(root.left.val==root.val) return root.right.val;
if(root.righn H M m C M wt.val == root.vJ P Xal) return root.left.val;
return Math.min(root.left.val,root.right.val)
};
  • 正确解法
/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.9 $ ^ m | : Q 5 Cright = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
//有0或2个叶子结点。
var findSecondMinimumValue = fuV r = ,nction(root) {
//没有结点
if(!root) return -1;
//只要一个根节点
if8 d F ; u h(!root.left&&!root.right) return -1;
//有两个叶子结点
let left = rooc q ?t.left.val;
let right = root.right.val;
if(left == root.val) left = findSecondMinimumValue(root.left);
if(right == root: 1 g.val) right = findSec?  U - & - ^ tondMinimumVa/ ! J  Cluey n N o 9 h e(root.right);
//左右子树都存在
if(leftA r R - { != -1, [ T 6 y P M k &]  ( w . S t a 6& right !=- 1) return Math.min(left, right);
// 只存在左子树
if(left != -1) return left;
//只存在右子树
return right;
};

第十九题-一棵树的每层结点平均值637

  • 标题:
给定一个非空二叉树, 回来O q n W S k : M一个由每层节点平均值组成的数组.
示例 1:
输入:
3& K I :
/ 
9  20
/  
15   7
输出: [3, 14.5, 11]
解说:第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因而回来 [3, 14.5, 11].

力扣(L& z WeetCode)

  • 解析:层序遍历,使用一个行列。两层循环,榜首层循环表明此刻的层次,第8 H h / 0 L2次循环是该层的结点树。将榜首层的结点入行列,取出核算平均值。然后将第二层的结点入行列,取出核算平均值。直到行列为空。
  • 回答
/**
* Definition foN - ] c * p j ` Dr a binary tree node.
* function TreeNode(val) {
*     this.v! T K val = val;
*     this.left = this.ri~ . s i B aght = nK ,  l $ = I ? Mull;
* }
*/
/**
层次遍历(同第10题的最小途径111-思路2)
*/
var averageOfLevels = function(root) {
let qJ o } O 4uene{ o W g U M 5 2 = [root];
let result = [];
while(quene.length){
let size = quene.length;let sum = 0;let node =null;
for(let i = 0; i< size; i++){
node= quene.shift();
sum+=node.val;
if(node.left) quene.pus? m F ~ x wh(node.left);
if(# u f a ] h )node.right) quene.push(node.right);
}
result.push(sum/size);a q 7 l n v ! y
}
return result;
};
  • 回答二:X J !使用DFS遍历完成:? [ x先序遍历,每次遍历的时分记载深度,构建一个二维数组arr[i][j],i表明当时深度,j表明当时深度的结点% ! 5值。最终对二维数组 j J D n B v的每一项reduce办法求得总和再使用map办法求出平均值。} a @ = i 3 _
var averageOfLevels = fun| 2 $ X v C *ction(root) {
let arr = [];
if(!root) return a6 ` 3rr;
const Deepfs = (root, level) =>Y ) _ * : h  3 {
(arr[level]||(arr[level]=_ 6 W r[])).push(rootz v ^ d H.val);
if(root.left)Deepfs(root.left, level+1);
if(root.right)Deepfs(root.righ5 ) 4 % D O ; It, level+1);| M y
}
DeeI n  E n - / i @pfs(root, 0);
return arr.map(item => { return item.reduce((pre, cur)=> pre+cur)/item.length});
};

第二十题-得到左} k { C { /下角的结点513

  • 标题
给定一个二叉树,在树的最终一行找到最左面的值。
示例 1:
输入:
2
/ 
1   3
输出:
1
  • 解析:与上面的标题类似。选用深度优先或许广度优先遍历树。广度优先遍历先让右子树入行列,再让左子l r = } B c树入行列。取出行列的最终一个元素便是最左面的子节点。这儿首要想说深度优先遍历,一种很v ! D * m $ h奇妙的思想便是即便更新树的深度,用result记载当时最深的榜首个结点值便是最左面的结点M 3 9 5 g b `值,当树遍历完后就回来result
  • 代码
var findBottomLeftValue = function(root) {
let maxLevel = -1;
let result = root.va} ; Q G C v 9 1 ^l
conS J Nst DFS = (root, level) => {
if(level>maxLevel) {
maxs ^ Z 0 5 7 + 4 JLevel = level;
result = root.val;
}
if($ x d Oroot.left) DFS(root.lH T h v )eft, leg N M %vel+1);
if(root.right) DFS(8 + F q f k ] V Oroot.k B j = h L } m 0right, level+1);
}
DFS(root, 0);
return result;
};

二叉查找树

第二十一题-修剪二叉查找树669

  • 标题
给定一个二叉查找树,一起给定最小鸿沟L和最大鸿沟R。经过修剪二叉查找树,使得一切节点的值J T R Q | ! T {在[L, R]中 (R>=L) 。你或许需求改动树的根u H @ g ,节点,所以成果应当回来修剪好的二叉查找树的新的根节点。
示例` 1 _ M p m 0 2:
输入:
3
/ 
0   4

2
/
1
L = 1
R = 3
输出:
3
/
2
/
1

力扣(LeetCode)

  • 解析:这个标题首要要知道二叉查找数是什么。二l ~ 3 v z } B 8叉查找数的根结点巨细是中心值,也便是根结点的左面都比根结点小,根结点的右边都比根结点大,修剪的成果=左子树修剪的成果和右子树修剪的成果。右子树修剪的成果便是右右子树修剪成果加右左子树修剪的成果。
  • 代码
//L和R便是左右鸿沟
var trimBST = funcV | % ) ; - [ 7tion(root, L, R) {
if(!root) return null;
if(root.val> R){
return trimBST(roo[  y h , ? 4 %t.left; b ! 0, L, Rf = B);
}else if(root.val<, ] t , q Q L){
return trimBST(root.right,6 U q | D b Z D x L, R);
}
root.left = trimBST(root.left, Lj Z E w 5 b % X e, R);
root.right = trimBST(root.right, L, R);
return root;
};

第二十二题S ( / l 4 ? k b m.寻觅二叉查找K / i 5 J树的第k个元素230

  • 标题) + Y u $ ` z `
给定一个二叉查找树,编写一个函数kthSmallest来查找其间第k个最小的元素。
阐明:
你可以假定 k 总是有用的,1 ≤ k ≤ 二叉查找树元素个数。
示例 1:
输入: root = [| O d , 0 w3,1,4,null,2], k = 1
3
/ 
1   4

  2
输出: 1

力扣(LeetCode)

  • 解析:二叉查找数的特点便是中序遍历有序,因而二叉查找树中序遍历后,第k-1个* t a m E _ B成果便是二叉查找树的第k小值。

  • 代码

var kthSmallest = function(root, k) {
let result=[];
if(!root) return ;
const helper = (root) => {
if(root.left) helper(root.left);
result.push(root.vN , 1 ual);
if(root.right) helper(root.right);
}
helper(root);
return r: z 9 $ W W Sesult[k-1];
};

第二十三题-把二叉查找树的每个结点的值加上比他大的结点值538

  • 标题
给定一个二叉查找树(Binary S~ l Z R 4 L q Zearch Tree),把它转化成为累加树(Greater Tree),使得每个节点的值是本来的节点值加上一切大于它的节点值之和
例如:
输入: 原始二1 _ G % F叉查r V L Y D ,找树:
5
/   
2     13
输出: 转化为累加树:
18
/   
20     13

力扣(LeetCode)

  • 解析:首要肯定是要遍历树的,怎么遍历。要知道最大值。咱们可以反中( $ X p % ^序遍历。右孩子,根结点,左孩子的次序进行遍历。遍历的时分记载当时结点值用sum表明。下一个结点root的结点值便是本身的val和sum的– ] /和。

31道二叉树算法,给自己的五一礼物
比方结点8的val便是8g ? M c c u Z h r+0,sum = val =8;然后遍历结点7的val便是7+sum=15,sum=val=15.然后结点4也是相同的。j C W / H ? J y g

  • 代码
if(!root) return root;
let sum = 0;
//遍历函数
const helper = (root)=>{
if(!root) return;
helper(root.right);
root.val+=sum;
sum = root.val;
helper( F F | V froot.left);
}
helper(root);
return rooh 1 @ ]  m 2 ]t
};

第二十四题-二叉查找树的最近公共先人235

  • 标题
给定一个二叉查找树, 找q @ f w ]到该树中两个指定节点的最近公共先人。
例如,给定如下二叉查找树: root =[6,2,8,0,4,7,9,null,null,3,5]
31道二叉树算法,给自己的五一礼物
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], pC f ) O 1 ] t 1 = 2, q = 8
输出: 6
解说: 节点 2 和节点 8 的最近公共先人是 6。

力扣(LeetCode)

  • 思路:可以递归也可以迭代。当pq的值小于根节点的值X m K 就在左子树中寻觅,假如pq的值大于根节点的值就在右子树中寻觅。这x F U B 9 r +儿要留意的是p和q是两个结点,不是结点值,比较的时分要用p.val。
  • 代码(非递归的迭代办S D 法)
var lowes& h 8t7 Y & [ 1CommonAncestor = function(root, p, q) {
//与上面逻辑Z # + u R C 9类似,可是是不断迭代更新root
while: / } % i(root){
if(root- * c - h :.val > q.val && root.val > p.val) root = root.left;
else if(root.val < q.val && root.val < p.val) root = root.right;
else{
return root;
}
}
};

第二十五题-从有序数组F ` ] N f W !中结构二叉查找树108

  • 标题
将一个按照升序排列的有序数组,转化7 O O A & O Q 0 P为一棵高度平衡a : d ~ I二叉查找树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的肯定值不超越 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个或许的答案是:[0,-3,9,-10,null,5],它可以表明下面这个高度平衡二叉查找树:
/ 
-3   9
/   /
-10  5

力扣(LeetCode)

  • 解析:这个标题要求结构高度平衡的二叉树,便是有序数组的中心值作为根节点。然后将1 N @ ] b y D z i数组分为两半,分别结构高度平衡的左之二叉树和高度平衡的右子二叉树。数组长h Y J 1 u u| S E 是奇数取中心值,数组长度是偶数取中心两个恣意一个。
  • , $ E V p L T
var sortedArrayToBST = function(nl G O wums) {
if(nums.length==0) return null;
const helper = (ng Y R } lums) =>! ~ T Q a # % T {
if(p m ) @ B !nums.length==0) return null;
let len = nums.length;
let i = Math.floor((len)/2);
let root = new TreeNode(nums[i]);
root.left = helper(nums.slice(0, i));
root.right = helper(nums.slice(i + 1));
return root;
}
return helper(nums);
};

第二十六题-依据有序链表结构二叉0 c V ` 3 ` n查找树109

  • { Z 9 P h d
给定一个单链9 s = A l I J }表,其间的元素按升序排序,将其转, D & w t A y O化为高度平衡的二叉查找树4 /  E X。
本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的肯定值不超越 1。
示例:
给定的有序链表: [-10, -3, 0, 5, 9],
一个或许的答案是:[0, -3, 9, -10, null, 5], 它可以表明下面这个高度平衡二叉查找树:
/ 
-3   9
/   /
-10  5

力扣(LeetCode)

  • 思想:依据有序链表结构二叉树没有有序数组灵敏,由于链表不可F V O %以像数组相同经过下标快速定位。所以咱们经过快慢指针,快指针每次前移两个结点,慢指针每次移动一个结点。当快指针是最终一个结点(链表长度奇数)快指针是倒数第二个结点(链表长度是偶数)U ^ P 0 O ( Y c的时分不再寻觅,此刻慢指针便是4 6 Q ? , C , ]中心方位。关于左面经过相# . g F ~ h同的方式找到左面链表的中心值,相同的方式找到右边链表c c * q k a的中心值。
  • 不知道有没有掘友有和我相L ( % U同的疑问,root.right = helper(slow.next, tail);//tail不能写成null为什么tail不直接写成null。毕竟关于右边的尾结点便是null啊。经过一番剖析后,榜首0 P R次找到中心值右边的链表尾结点确实是tail,可是关于榜首次中心值左面的链表尾结点tail便是slow指向的方位啦。因而写null是不对的。
  • 代码
/**
* @param {ListNode} head
* @return {TreeNode}
*/
var sorm K M u 2 E C BtedListToBST = function(head) J E X U ~ r 4 n) {
iJ j uf(!head) r!  % D : p  {eturn null;
const helper = (heap 9 r b Gd, tail)=&O K 1gt; {
if(head == tail) return null;
le7 N dt fast = head, slow = head;
//对e : V @ X O _应链表是偶数和奇数两种s u )状况
while(fast!=tail && fast.next != tail){
fast = fast.next.next;
slow = slow.next;
}
let  root = new TreeNj W ? + 0 , @ode(slR _ l A j & zow.val);
root.left = helper(head, slow)t y . 7 ;
root.rN Y L G Night = helper(sla ( { Z % ,ow.next, tail);//tail不能写成null
return root;
}
return helper(head, null);
};

第二十七题-在二叉查找树中寻觅两个结点,使H b e他们的和为一个给定的值653

  • 标题
给定一个二叉查找树和一个方针成果,假如 BST 中存在两个元素且t i g它们的和等于给定的方针成果,则回来 true。
案例 1:
输入:
5
/ 
3   6
/    
2   4   7
Target = 9
输出: True

力扣(LeetCode)

  • 解析:两种思路,榜6 $ h 3 m W . X c首种将平衡树结点值转化成有序; m . q l _数组,然后使用快慢指针。第1 b r – E二种思路是遍历树的每一个结点,用Set记载遍历的每一个结点值。假如k-当h N p 4 0 _ 5 *时结点值的成果存在与Set结构中。那么就阐明存在这样的两个结点。假如结点遍历完都还没有就回来false。
  • 代码
va~ r :r findTarget = function(root, k) {
if(!root) return false;
let s = new Set();
const helper  = (root, k, s) => {
i5  ] Bf(!root) return false;
if(s.has(k-root.val)) return true;
s.add(root.val);
return helper(root.left, k, s) || helper(root.right, k,s);
}
return helper(root, k, s)
};

第二十八题-在二叉查找树中查两个结点的最小肯定值530

  • 标题
给你一棵一切P q r E & b x m I节点为非负值的二叉查找树,请你核算树中恣意两节点的差的肯定值的最小值。
示例:
输入:
1

3
/
2
输出:
1
解说:
最小肯定差为 1,其间 2 和 1 的差的肯定值为 1(或许 2 和 3)T m m w K

力扣(LeetCode)

  • 解析:肯定值差的最小值必定呈现在二叉查找树中序遍历恣意相邻的两个结点中。因而对二叉树中序遍历,并将当时结点值减去上一个结点值作为差的最小值。遍历每一个结点跟新最小值min。
  • 代码
var getMinimumDifference = function(root) {
// if(!root) return Number.MAX_w + N R @ hVALUE;
let min = Number.MAX_VALUE;
let prenode = null;
const helper = (root) => {
if(root.left) helper(root.left);
if(prenode) min = Math.min(min, root.vw y M V 3 E 2 eal - prenode.va/ | ul);
prenode| D @ c j = root;
if(root.right) helper(root.right);
}
helper(root);
return min;
};

第二十九题-寻觅二叉查找树中次数呈现最多的值501

  • 标题:在一根二叉查找树中回来呈现结点次数最多的结点。假定二叉O s 6查找树的界说使左子树小于等于根节点,右子树大于等于根节点。
  • 解析:中序遍历的成果是有序的。不或许呈现[1,2,2,3,4,2,2,5]这样的序列,因而遍历每一个结点j s j L , =。假如当时结点val等于前一个结点的v= ~ 6 s 8 J o /al。那么就将呈现次数count++,假如不等便是一个新的值,让count=1。再经| 4 & : Y &过count和max比较巨细。max是当时众数结点呈现的次数。假如count比max$ T w c | y = _还要大就找到了一个新的成果。假如持平就找到了相同的成果。假如count比max小就持续遍历下一个结点。对下一个结点进行相同的判别直到结点遍历完。V j 8 , } [
  • 代码
var findMode = function(root) {
// 1.中Y v V y i序遍历当时值和上一个值比较是否相同。相同则Q p | L p _ B @加1,不% 4 / ) ) z U相同count便是1表明当时是一个新元素
//没比较一次就要看是否更新最大值S j :
//假如count>max就更新最大值,清空成果数组,增加新的数据到成果2 ^ 1数组
//假如c{ P &ount= max就阐明当时出新次数和之9 | m W j [前呈现的次数相同多,直接增加新数据到成果数组
let prenode = null;
let count = 1;
let max = 1; let res = [];
const helper = (roo6 - b ;t) => {
if(!root) return;j O _ * a f B
helper(rooA T 6 6 F 2 C f Nt.lv _ ) ! ( Qeft);
if(prenode) {
if(root.val==prenode.val) count++;
else count=1;
}
if(count >+  ! ? v max){
max =s a Y p G e count;
res = [];
res.push(root.val);
}else if(count == max) res.push(root.val);
prenode = root;
helper(rootv d 7 R n !.right);
}
helper(root);
returc b C B D 5n res;
};

公共先人

还记得* H X ] / S (第二十四题的二叉查找树的2 w * G A O d j K公共先人吗,上面咱们运用迭代的方式完成,这儿运用递归p r v B P – f完成普通二叉树的公共先人

第三十题-二叉树的最近公共先人236

  • 标题:给定一个二叉树, 找到该树中两个指定节W g C 4 X点的最近公共c Y f 0 2 w d先人。
    l` T f y ` A jeetcode第236题
  • 剖析:看当时结点值是否等于q和p中恣意一个的结点值。假如等于那么公共先人便是当时结点,假如不等看看左子树和右子树中是否存在p和q,判别逻辑在代码的注释中+ ^ d n L v : b,别的依据标题f } J b P ? A咱们可以知道不会呈现p和q不属于二叉树结点的状况。
  • 代码
/**
* @param {2 U { i f 4 | M 9TreeNode} ro v . d d c N =ot
* @param {TreeNod} 3 f D G +e} p
* @param {TreeNode} q
* @return {TreeNode}
*/
vz y ) ( i $ar lowestCommonAncestor = functio: 2 1 |n(root,8 ) | p, q) {
if(!root || root.val == p.va: e [ Vl || ra J J d E F * 3oot.val == q.val) return root;
let left = lowestCommonAncestor(root.left, p, q);
let right = lowestCommonAncestor(root.right, p, q);
//假如left不存在p_ p e & a ; D v A或q就回来right的成果。假如left存在,right不存在就回来left成果。假如le9 : x Rft和right都存在就回来根( Z E 6 l Q H节点
if(left == null) return right;
else if(right == null) rA _ ~ / v F P S xeturn left;
return root;E + / @
};

前缀树

第三十一题-完成一个tire208(mid)

  • 标题
完成一个 Trie (前缀树),包含insert,search, 和startsWith这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 回来 true
trie.search("apJ ^ g = c _ }p");     // 回来 false
trie.st[ 6 } [ NartsWith("app"); // 回来 true
trV ) d u k ^ie.insert("app");
trie.sear q i # a u ;rch("app");     // 回来 true
阐明:
你可以假定一切的输1 l 8 * * 8 2入都是由小写字母a-z构成的。
确保一切输入均为非空字符串。

力扣(LeetCode)

  • 剖析:前缀树又称字典树。文章开头也有阐明

又称单词查找树,Trie树,是一种树形结构,是一种K % , z x R哈希树的变种。典型应用是用于核算,排序和保存很多的字符串(但不仅限于字符串m P r $ b m Q D n),所以经常被查找引擎系统用于文本词频核算y h A X S M 4。它的长处是:使用字符串的公共前缀来削减查询时刻,最大限度地削减无谓的字符串比较,查询效率比哈希树高。—-《百度百科》

  • 解析:这或许是这些标题里边最杂乱的一道题,由于要写三个函数@ – & ? ;f – U ( 5 i # k K其实最要害的的insert函数可以写出来那么后边的两个函数也是相同的。我将代码里边写上注释,假如有当地必定要在谈论区c0 W I V sall我。

  • 代码

  • js完成

//界说trie树h q {的结构
function Trie(val) {
//每一个结点都Z @ n N ~ I |最多有26个孩子,用数组存
this.next  = new ArG x + - X o dray(26);
//是否是叶子结点,默许false
this.isEnd = false;
//结点值,是一个字符类型
this.val = val;
};
/**
* Inserts a word into the trie.
* @p/ 2 m M f 1 ] g xaram {string} word
* @return {v* $ 1 T k 2 e X Uoid}
*/
Trie.prototype.insert = function(word) {
let len: x  d P 6 = word.length;
//node表明当时的trie结点
let node = this;
for(let i = 0; i< len; i++) {
//word[i]是一个字符串类型,charCodeAt办法将他转化成Ascii码
//比方字符b的ascii码是98,那么n=1/ w 0 = g R ] P r;
let n = word[i].charCodeAt()-97;
//假如node孩子结点中已经存& U q / l n V G `在这个字符就让当时的trie等于这个结点的孩子trie
//假如node孩子节点数组中不存在咱们就结构这样的一个trie
if(node.next[n] &ams d k v hp;& node.next[n].val==word[i]){H 5 E
node = now $ c # l % ~d` # 2 / ^e.nexF j f / 9 = V 0t[n]
}else {
node.next[n] = new TriA J { Je(word[i]);
node= node.n2 t 4 H I Zext[n];
}
}
//结构完毕让最终一个trie的isEnd特点符号为true,表明最终一个结点
node.y P 6 aisEnd = true;
};
Trie.prototype.sY 5 rearch = function(word) {
if(!word) return false;
let len = word.length;
let node = this;
let result = true;
for(let i = 0; i < len; i++) {
let n = word[i].chB v { `arCodeAt()-97;
if(no1 s l T tde.next[n]&&node.next[- ? Xn].val==word[i]) {
node = node.next[n];
}
else {
result = fa- w Plse b 4;
break;
}
}
//search的时分假如次数result是true还要判别此刻node是否是前缀树的叶子结点,假如不是还是会回来false
if(re[ n V } tsult) result = node.isU C U F / y | PEnd;N K : D ( = n
return resultM d ? / $ % R U;
};
//search明白了这个函数也就明白了
Tri!  w D | C B 0 !e.prototype.! ; XstartsWith = function(prefix) {
let len = prefix.length;
let node = this;
let res? 1 Qult = true;
for(let i = 0; i < len; i++) {
let n = prefix[i].charCodeAt()-97;
if(node.next[n]) {
node = node.next[n];
}
else {
result = false0 i a @ x P E 8;
break;
}
}
return result;
};
  • java完成
class Trie {
// 当时节点的值
public char value;
//a-z有26个字母,需求拜访时由于a的ASCII码为97,所以一切字母拜访的对应下标皆为 字母的ASCII码-97
public Trie[] children=new Trie[26];
// 标识此节点0 3 q C Z n : g .是否为某个单词_ L p S ; M &的完毕节点
public boolean endAsWord=false;
public Trie() {
}
publicU % 2 W @ F y 9 2 void insert(String word) {
if(word!=null){
//分解成字符数组
char[] charArr=word.toCharArray();
//模仿指针操作,记载当时拜访到的树的节点
Trie currentNode=this;
for(int i=0;i<charArv i F I E o  j (r.length;i++){
char currentChar=charArr[i];
//依据字符获取对应的子节点
Trie node=currentNode.cm Z ) shildren[currentChar-97];
ifI U 0 N ~ H c(node!=null && node.value==currentChar){//判别节点是否存在
currentNode=nodC ( % q Y t ^e;
}else{//不存在则创建一个新的叶子节点,并指向当时的叶子节j , c U ~点
node=new Trie();
node.value=currentChar;
currentNode.children[currentChar-97]=node;
currentNode=node;
}H b c = d {
}
//这个标识很重要,将最终叶子结点符号true在后边的serach中有用
currentNode.endAsWord=true;
}
}
public boolean search(String word) {
boolean resultq Y 8 M [ | f=true;
if(word!=null && !word.trim().equals("")){
char[] prefixChar=word.toCharArray();
Trie currej 9 ^  :ntNode=this;
for(int i=0;i<prefixChar.length;i+n | S L $+){
char currentChar=prefixC7 8 4  $har[i];
Trie node=currentNode.children[currentChar-97];
if(node!=null && node.value==currentChar){//判别节f n R e =点是否存在
cG U % M /urrentNode=node;
}else{
result=false;
break;
}
}
if(result){
result=c. n _ h Q ( f DurrentNode.endAsWord;
}M 3 W ;
}
return resulte P T P l z 6 , s;
}
public boolean startsWith= W K 0 r V U ;(Stt Q 0 G d = lring p[ N X jrefix) {
boolean result=true;
if(prefix!=null && !prefix.trim().equals("t 4 ^ H @ { T")){
c7 i d d : e $ 1har[] prefixChar=prefix.toCharArray();
Trie currentNode=this;
for(int i=0;o v U v T M Ui<prefixChar.length;i++){
char cuV w N F 4 i orr9 Z t = UentChar=prefixChar[i];E p ; o ; d ? d ]
Trie node=c% # K uurrentNode.children[currentChar-97];
if(node!=null && node.valueW J G 3==currentChar){//判别节点是否存在
currentNode=node;
}else{
rD . V r C eesul] 5 b } |t=false;
break;
}
}
}
return result;
}
}

额定弥补:尾递归

我们都知道递归简单栈溢出,由于函数入栈后还没有毁掉又入栈,递归的次数决定了你开辟栈的空间,所以假如递归次I y + W – 5数很: S O多就简单栈溢出。

所以就有了尾递归。那么什么是尾递归,尾递归来历于尾调用,尾调{ X H用在《ES6规7 a J范入门一书》里边有详细阐明,便是说一个函数A的尾部回来的一个函数B,而且函数B不会用到函数A的内部变量,由所以A函数的最终一步,那执行B函数的时分就毁掉A的执行栈。由于调用方位和内部变量都不会再用到了,直接运用内层函数的调用栈替代外层函数就可以。

这有一篇我觉得讲的很好了解的尾递归和时0 ( w E 1 I 0刻杂乱度的文章共享给我们
尾递归

最终

最终说一点个人关于算法的感触。

算法刚开端真的很难,可是到后边入门了会发现有了思想会觉得算法度一件很风趣的工作,特别是当空间杂乱度和时刻杂乱度打败100%的时分挺高兴的。

刚开端的时分底子无法了解递归的思想,我只能人脑入栈,手动画图写代码,把每一步都6 ` S c F A y y写出来。成果一天就过去了,有时分能把自己写晕,俺便是个渣渣‍♂️

别的还有两点想说

  • 树的遍历与五种状况,上面一切的标题归根到底都是树的X 7 C 2 S {遍历。
  • 写算法题要细心
    ,做算法要耐心和坚持

假如上面的标题您还没有操练,那就花很多的时刻去操练吧。这些标题假如自己能写出来,我想后边做算法会越来越快滴(大佬请绕行)

假如关j j 2 , P v于里边的标题有哪些当地不g – Y _ = n – k /了解,直接谈论呼叫我,假如讲不铲除骂我渣男就好了~

最终送上一个迟到的五一国际K ; | C ^ 6 R劳动节高兴,愿我们拥有一个充实的假期‍~

本文运用 mdnice 排版

附:曾| z W J m y i J C经人脑入栈进行递归的样子‍♀️…️

31道二叉树算法,给自己的五一礼物

发表评论

提供最优质的资源集合

立即查看 了解详情