码solution

中序与后序遍历序列构造二叉树思路及代码solution相关题目

654

二叉搜索树相关700.二叉搜索树中的搜索算法思路与代码solution

本文是基于代码随想录上二叉树章节的所有例题及其对应的算法思路序号代表的是力扣题号

我写在最前面

labuladong二叉树纲领篇——遇到一道二叉树的题目时的通用思考过程是

traverse

2、是否可以定义一个递归函数通过子问题子树的答案推导出原问题的答案如果可以写出这个递归函数的定义并充分利用这个函数的返回值。

3、无论使用哪一种思维模式你都要明白二叉树的每一个节点需要做什么需要在什么时候前中后序做。

226.翻转二叉树

我们既然需要翻转整颗二叉树那么我们不妨先翻转左子树在翻转右子树然后将跟节点的左右子树交换即可这样就好啦

solution

而且我们需要在往下去递归之前做这件事情也就是在前序位置去交换左右节点

/***

invertTree(root-left);TreeNode*

left

invertTree(root-right);root-rightright;root-leftleft;return

root;}

遍历二叉树交换每个节点的子节点traverse(root);return

root;}//

遍历框架去遍历左右子树的节点traverse(root-left);traverse(root-right);}

};101.对称二叉树

我们先不管代码怎么实现我们是不是同样遍历一遍二叉树就可以把这个问题解决掉

solution

对于这道题目我们首先是不是同样可以用遍历的思路来解决终止条件就是到达叶子节点我们只需要一个traverse函数和一个外部变量来实现就行在刚刚进入一个结点的时候前序位置去更新我们的maxdepth在离开一个节点之前后序位置去维护depth。

class

depth);traverse(root-left);traverse(root-right);//

后序遍历位置depth--;}

我们要求一颗二叉树的最大深度我们只需要分别知道它的左右子树的最大深度即可然后return

class

currentDepth);}traverse(root-left);traverse(root-right);//

撤销选择在离开节点时减少当前深度currentDepth--;}public:int

minDepth(TreeNode*

我觉得有了上一题的铺垫首先应该是想到这种办法思路也非常明确就是想找到左右子树各自的最小深度然后再加上根节点

但是力扣给的示例没有全部通过它给的示例是一颗斜树准确的来说是条五个节点的链表这种就是极端的情况我们怎么去解决它呢

0的情况发生参照下面的预期结果所以我们就需要在即将离开一个节点之前判断此时的左右子树是否为空也就是leftmin/rightmin为0的情况

leftmin0那么我们就return

是因为在求最大深度时我们的出口是到叶子节点就行一股脑的往下冲不会面临着是否为空的问题

而我们要求最小深度时其实更像是一个探险的人需要一步一步地走需要避开危险

deepseek

最小深度中当左子树为空时(root.left为None)右子树的深度决定了当前节点的最小深度。

同理处理右子树为空的情况。

只有左右子树均存在时才取较小值加1确保路径有效。

关键

最大深度直接取左右子树的最大值加1无需特殊处理空子树因为空子树的深度0不会影响非空子树的最大值结果

修改之后AC

rightminminDepth(root-right);int

leftminminDepth(root-left);if(leftmin0){return

rightmin1;}if(rightmin0){return

leftmin1;}return

读完这道题我就有思路了就是把左右子树的分别有多少个节点给他算出来然后相加不就行了吗

确实能AC也很简单

意味着我们其实是可以利用完全二叉树的特性来解决问题的这才是这题高效率的关键因此就有了solution2

class

rightcountNodes(root-right);int

result;}

假如你学习过懒猫老师的课程你一定知道如果给你一个满二叉树的深度k那么它的节点数就是2的k次方-1而给你一个二叉树的层数x那么这一层有2的X-1次幂

个节点

对于这道题其实不用想的太复杂还是一样就问你是不是遍历一遍就可以判断是否为二叉平衡树了怎么判断呢是不是把两个左右子树高度搞出来然后比较一下就行了代码上就是借助一个外部变量然后一个compare函数就行

我们需要知道这个compare函数帮我们做了什么事情需要明确给出这个函数的定义返回以该节点为根节点的二叉树的高度如果不是平衡二叉树了则返回-1

不然就很容易被绕进去

如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢当然是其左子树高度和其右子树高度的差值。

分别求出其左右子树的高度然后如果差值小于等于1则返回当前二叉树的高度否则返回-1表示已经不是二叉平衡树了。

class

leftcompare_height(root-left);if(left-1){return

-1;}int

rightcompare_height(root-right);if(right-1){return

-1;}return

compare_height(root);if(result!-1){return

true;}else{return

这也是labuladong在它的文章中提到的二叉树与动态规划和回溯算法之间的关系

算法思路及代码

root-rightnullptr)//叶子节点{return

0;}int

leftsumsumOfLeftLeaves(root-left);if(root-left!nullptr

root-left-rightnullptr){leftsumroot-left-val;}int

rightsumsumOfLeftLeaves(root-right);int

sum;}

一个find函数和一个变量depth就能解决问题其次我们需要确定这个函数的终止条件递归的出口是不是当遇到叶子节点的时候就需要更新depth了用一个result记录此时深度最左边节点的值再次我们需要给这个find函数一个明确的定义就是给一个根节点返回最大深度最左边孩子的值细节方面

所以还是采用前序遍历先给MAXdepth先定义成最小的整型确保MAXdepth能够正常更新

result同理

root-rightnullptr){//如果找到叶子节点更新最大深度if(depthMaxdepth){Maxdepthdepth;resultroot-val;}return;}if(root-left!nullptr){depth;//前序位置traverse(root-left,depth);depth--;//后序位置

回溯在离开节点时维护depth}if(root-right!nullptr){depth;traverse(root-right,depth);depth--;}return;}int

root)

弄个node指向每一层的第一个节点result记录每次node指向的值直到队空停止循环

class

我们需要判断二叉树中是否存在从根节点到叶子节点的路径使得路径上所有节点值的和等于给定的目标和

targetSum。

我们可以通过递归的方式实现这一点具体来说使用前序遍历根-左-右来遍历二叉树。

详细步骤

一开始我想用一个vector向量来保存每次递归到叶子节点sum的值

也就是说需要遍历出所有路线然后在主函数中for循环遍历我们的vector

true

向量中record.push_back(sum);return;}//

sum,

因为我们一开始在学习二叉树的前中后序遍历时一般都是给我们一颗二叉树

如果不明白C

相信你一定对于这题有了最基本的认知只不过对于代码实现还是不太清楚

给你一个前序后序

哈希表inpos的作用就是存储中序遍历的值与其位置的映射比如说后序遍历的最后一个元素是根节点

solution

使用哈希表存储中序遍历中每个值的位置以便快速查找根节点在中序遍历中的位置unordered_mapint,intinpos;

public:/***

i0;in;i){inpos[inorder[i]]i;}//

build(inorder,postorder,0,n-1,0,n-1);}/***

param

如果中序遍历的左边界大于右边界说明已经没有节点返回空指针if(ilir

plpr){return

递归构建左子树root-leftbuild(inorder,postorder,il,ilk-1,pl,plk-1);//

递归构建右子树root-rightbuild(inorder,postorder,ilk1,ir,plk,pr-1);//

root;}

constructMaximumBinaryTree([3,2,1,6,0,5])

{//

constructMaximumBinaryTree({3,2,1});root-right

constructMaximumBinaryTree({0,5});return

root;

中的最大值就是根节点然后根据索引递归调用左右数组构造左右子树即可

TreeNode*

constructMaximumBinaryTree(vectorint

nums)

constructMaximumBinaryTree(nums[0..index-1]);root-right

constructMaximumBinaryTree(nums[index1..nums.size()-1]);

}前序后序不唯一

postorder[postStart..postEnd]//

build(vectorint

TreeNode(preorder[preStart]);}//

root

根据左子树的根节点索引和元素个数推导左右子树的索引边界root-left

build(preorder,

*每个二叉树节点都可以认为是一棵子树的根节点对于根节点首先要做的当然是把想办法把自己先构造出来然后想办法构造自己的左右子树。

maxVal从而把根节点

constructMaximumBinaryTree(vectorint

nums)

{//递归终止条件只有一个元素的时候if(nums.size()1)return

new

i0;inums.size();i){if(nums[i]maxval){maxvalnums[i];indexi;//不断更新maxval//直到遍历完整个数组找到最大值}}TreeNode*

rootnew

TreeNode(maxval);//递归创建左子树if(index0){vectorintvec(nums.begin(),nums.begin()index)

;//创建一个数组来存储左子树元素范围root-leftconstructMaximumBinaryTree(vec);}//右子树if(indexnums.size()-1)//说明至少还有一个元素{vectorintvec2(nums.begin()index1,nums.end());root-rightconstructMaximumBinaryTree(vec2);}return

root;}

**************************************

class

constructMaximumBinaryTree(std::vectorint

nums)

searchBST(root-left,val);}if(root-valval){return

searchBST(root-right,val);}return

nullptr;}