列构造二叉树中等

输出[1,null,2,null,3,null,4,null,5,null,6]示例

输入root

1.由于前序遍历的顺序是【根-左子树-右子树】中序遍历的顺序是【左子树-根-右子树】所以由上图的前序遍历preorder可知它的第一个元素3为根节点。

那么由中序遍历inorder可知根节点3的左侧元素为左子树共1个元素根节点3的右侧元素为右子树共3个元素。

2.记录3的左子树的前序遍历顺序和中序遍历顺序其中9即为3的左节点

记录3的右子树的前序遍历顺序和中序遍历顺序其中20即为3的右节点

3.记录20的左子树的前序遍历顺序和中序遍历顺序其中15即为20的左节点

记录20的右子树的前序遍历顺序和中序遍历顺序其中7即为20的右节点

举例说明

mp[preorder[pre_root]];TreeNode*

root

TreeNode(preorder[pre_root]);//左子树节点个数int

size_l

不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。

输入root

[10,5,-3,3,2,null,11,3,-2,null,1],

targetSum

[5,4,8,11,null,13,4,7,2,null,null,5,1],

targetSum

和为K的子数组类似使用前缀和哈希表的方式来解决只不过我们现在面对的数据是存储在二叉树里面了

注unordered_maplong,

解释节点5和节点4的最近公共祖先是节点5。

因为根据定义最近公共祖先节点可以为节点本身。

示例

输入root

按照p、q中一节点是否是另一节点的祖先节点可以分为上图两种情况

5.如果当前节点左、右子树均返回空返回空

被定义为一条节点序列序列中每对相邻节点之间都存在一条边。

同一个节点在一条路径序列中

至多出现一次

贡献值可以理解为以该节点为起点在其子树中寻找一条路径使其路径和最大

对空节点而言getNum(NULL)0