从前序与中序遍历序列构造二叉树

定义一个空字符串str用于存储结果。

首先检查输入的根节点是否为nullptr如果是则直接返回空字符串。

处理非空根节点

如果根节点不为空将根节点的值转换为字符串并添加到str中。

然后检查左子树是否存在

如果左子树存在root-left不为nullptr在str中添加左括号(递归调用tree2str处理左子树并将结果添加到str中最后再添加右括号)。

如果左子树不存在但右子树存在root-left为nullptr但root-right不为nullptr在str中添加()以表示左子树为空但右子树存在。

接着检查右子树是否存在

如果右子树存在root-right不为nullptr在str中添加左括号(递归调用tree2str处理右子树并将结果添加到str中最后再添加右括号)。

class

to_string(root-val);if(root-left)

{str

二叉树的层序遍历多了一个条件把每一层都存放在一个二维动态数组中主要是控制每一层的个数然后放入vector中在把每个vector放入vector的vector中。

层序遍历依靠队列来实现当访问根的时候出根节点然后把该节点的左右节点分别入队记住这里队列存储的是二叉树节点的指针而不是该节点的值这是因为在遍历的过程中需要访问左右子节点。

front-val

vv;if(root)q.push(root);while(!q.empty())

{int

q.front();q.pop();v.push_back(front-val);if(front-left)q.push(front-left);if(front-right)q.push(front-right);}vv.push_back(v);}return

vv;}

该题和二叉树的分层遍历1是一样的只需要把最后的存储在二维动态数组中的值逆序

class

q;if(root)q.push(root);while(!q.empty())

{vectorint

q.front();q.pop();v.push_back(front-val);if(front-left)

{q.push(front-left);}if(front-right)

{q.push(front-right);}}vv.push_back(v);}reverse(vv.begin(),vv.end());return

vv;}

的孩子时当前节点就是祖先反之亦然。

这是因为在二叉树中如果一个节点是另一个节点的直接子节点那么它们的共同祖先就是父节点。

当

分别在当前节点的左右子树中时当前节点就是它们的祖先。

这是因为从根节点开始向下遍历只有当两个节点分别位于不同子树时当前节点才是它们的最低公共祖先。

二、情况

如果一个节点的值比当前节点小另一个节点的值比当前节点大那么当前节点就是它们的祖先。

这是因为二叉搜索树的特性是左子树节点的值小于根节点的值右子树节点的值大于根节点的值。

所以当两个节点分别位于当前节点的两侧时当前节点必然是它们的最低公共祖先。

例如在一个二叉搜索树中当前节点值为

10p节点值为

如果两个节点的值都比当前节点小那么递归到左子树中去找祖先。

因为二叉搜索树的特性值小的节点必然在左子树中。

同理如果两个节点的值都比当前节点大那么递归到右子树中去找祖先。

例如当前节点值为

10p

a当一个节点在当前节点的左子树另一个节点在当前节点的右子树时当前节点就是它们的祖先。

这与公共祖先的特征一致因为在普通二叉树中没有特定的大小关系只能通过遍历整个树来确定最低公共祖先。

例如在一个普通二叉树中当前节点有左子树和右子树p

在左子树中q

如果两个节点都在左子树递归到左子树中查找如果两个节点都在右子树递归到右子树中查找。

这是因为在普通二叉树中没有特定的顺序只能通过逐步遍历子树来确定最低公共祖先。

例如当前节点有左子树和右子树p

都在左子树中那么需要在当前节点的左子树中继续查找它们的最低公共祖先。

方法一

这种方法比较直观先判断节点是否在树中然后再根据节点的位置来确定最低公共祖先

class

lowestCommonAncestor(root-left,p,q);if(pInRight

qInRight)

lowestCommonAncestor(root-right,p,q);return

nullptr;}

lowestCommonAncestor(root-left,

q);//

lowestCommonAncestor(root-right,

q);//

lowestCommonAncestor(root-left,

q);if

lowestCommonAncestor(root-right,

q);return

右会产生一个有序的节点序列。

在converList函数中通过递归实现中序遍历。

在遍历过程中当处理每个节点时利用一个引用参数prev来连接节点。

例如当prev不为nullptr时prev

right

prev这两个操作就把当前节点cur和之前的节点prev双向连接起来。

这样就按照中序遍历的顺序逐步构建了链表的中间部分。

找头节点和尾节点步骤②

由于中序遍历的第一个节点是最左节点所以遍历二叉树找到最左节点作为链表的头节点是合理的。

从逻辑上来说这个最左节点在二叉搜索树中是值最小的节点。

同样在找到头节点后通过不断地沿着节点的右指针移动最终可以找到最右节点它将作为链表的尾节点。

返回头节点步骤③

因为头节点是中序遍历的第一个节点而中序遍历是升序排列节点值的所以这个头节点的值是整个链表也就是原来二叉搜索树中序遍历后的节点序列中的最小值。

返回头节点就可以作为整个循环双向链表的起始点方便后续对链表进行操作。

class

return;converList(cur-left,prev);if(prev)prev-right

cur;cur-left

cur;converList(cur-right,prev);}

Node*

nullptr;converList(root,prev);Node*

head

前序遍历的特点是先访问根节点然后是左子树最后是右子树。

所以前序遍历结果中的第一个元素一定是整棵树的根节点。

中序遍历的特点是先访问左子树然后是根节点最后是右子树。

通过在中序遍历中找到根节点的位置可以确定左子树和右子树的元素范围。

二、构建步骤

首先从前往后取前序遍历结果中的第一个元素创建一个新的节点作为当前子树的根节点。

然后在中序遍历结果中找到这个根节点的值以确定左子树和右子树的范围。

在中序遍历中根节点左边的元素构成左子树右边的元素构成右子树。

接着对于左子树

根据确定的左子树范围在前序遍历结果中找到对应左子树的起始位置在前序遍历中根节点后面的一段连续元素是左子树的前序遍历结果。

递归调用构建函数传入左子树的前序遍历和中序遍历结果以及对应的范围构建左子树并将构建好的左子树连接到根节点的left指针上。

对于右子树

类似地确定右子树在前序遍历中的起始位置在前序遍历中左子树部分之后的连续元素是右子树的前序遍历结果。

递归调用构建函数传入右子树的前序遍历和中序遍历结果以及对应的范围构建右子树并将构建好的右子树连接到根节点的right指针上。

重复以上步骤直到所有子树都构建完成。

class

prei,inbegin,rooti-1);elseroot-left

nullptr;if(rooti

prei,rooti1,inend);elseroot-right

nullptr;return

_buildTree(preorder,inorder,prei,inbegin,inend);}

从中序与后序遍历序列构造二叉树

根”。

当构建右子树时--end操作是为了更新后序遍历的索引使其指向右子树的最后一个节点在构建右子树的递归调用中。

因为后序遍历的特性一旦处理完根节点也就是当前正在构建的节点下一个节点要么是右子树的根节点如果有右子树要么是左子树的根节点如果没有右子树。

在构建右子树后end已经指向了左子树的最后一个节点不需要额外的--end操作就可以正确地开始构建左子树。

中序和前序遍历构建二叉树的情况推测你这里的prev是类似prei用于前序遍历索引

右”。

在构建二叉树的递归过程中每次构建一个子树时需要先处理根节点然后是左子树最后是右子树。

当构建左子树时prei操作是为了将索引移动到左子树的根节点在前序遍历序列中。

而在构建右子树时同样需要prei操作来将索引移动到右子树的根节点因为前序遍历序列中左子树节点之后才是右子树节点。

这是由于前序遍历的顺序决定的需要不断更新索引来按照正确的顺序获取子树的根节点。

class

nullptr)return;v.push_back(root-val);_preorderTraversal(root-left,v);_preorderTraversal(root-right,v);}vectorint

root)

ret;_preorderTraversal(root,ret);return

ret;}

创建一个空的结果向量ret用于存储遍历结果。

创建一个栈st用于辅助遍历。

使用一个指针cur指向当前正在处理的节点。

进入循环只要当前节点不为空或者栈不为空就继续循环。

第一个内部while循环用于遍历左子树

ret表示访问了该节点先访问根节点。

将当前节点压入栈中为后续访问右子树做准备。

将当前节点指向其左子树继续遍历左子树。

当左子树遍历完后当前节点cur为空此时从栈中弹出一个节点top这个节点是上一个被访问的节点的父节点。

将当前节点cur指向弹出节点的右子树进行下一轮循环开始遍历右子树。

class

{//1、先访问树的左路节点//2、再访问左路节点的左子树while(cur){ret.push_back(cur-val);st.push(cur);

cur-left;}//取栈中的左路节点的右子树出来访问TreeNode*

top

与前序遍历类似就存在一些细微的不同就是访问顺序。

(唯一变化的就是访问节点的时机)

右子树通过迭代的方式再分成左路节点和左路节点的右子树的方式访问。

1、左路节点(入栈)

{//1、左路节点入栈先不能访问(中序)while(cur){st.push(cur);cur

cur-left;}//2、取出栈中节点访问和节点的右子树TreeNode*

top

st.top();st.pop();ret.push_back(top-val);cur

top-right;}return

左路节点的访问所以还需要加一个条件右为空可以访问右访问过了也可以访问

lastNode

记录上一次访问的节点以确定何时处理当前节点。

如果不加这个指针处理就是重复拿到栈中的左路节点的值

class

{ret.push_back(top-val);lastNode

top;st.pop();}