攀枝花建设集团网站,山西seo排名,福州网站建设嘉艺,域名更新目录
1. 二叉树创建字符串。
2. 二叉树的分层遍历1
3. 二叉树的分层遍历2
4. 二叉树的最近公共祖先
5. 将二叉搜索树转换为排序的双向链表
6. 从前序与中序遍历序列构造二叉树
7. 从中序与后序遍历序列构造二叉树
8. 二叉树的前序遍历#xff0c;非递归迭代实现
9.…目录
1. 二叉树创建字符串。
2. 二叉树的分层遍历1
3. 二叉树的分层遍历2
4. 二叉树的最近公共祖先
5. 将二叉搜索树转换为排序的双向链表
6. 从前序与中序遍历序列构造二叉树
7. 从中序与后序遍历序列构造二叉树
8. 二叉树的前序遍历非递归迭代实现
9. 二叉树的中序遍历非递归迭代实现
10. 二叉树的后序遍历非递归迭代实现 1. 二叉树创建字符串。
. - 力扣LeetCode 初始化字符串并处理空树情况 定义一个空字符串str用于存储结果。首先检查输入的根节点是否为nullptr如果是则直接返回空字符串。 处理非空根节点 如果根节点不为空将根节点的值转换为字符串并添加到str中。然后检查左子树是否存在 如果左子树存在root-left不为nullptr在str中添加左括号(递归调用tree2str处理左子树并将结果添加到str中最后再添加右括号)。如果左子树不存在但右子树存在root-left为nullptr但root-right不为nullptr在str中添加()以表示左子树为空但右子树存在。接着检查右子树是否存在 如果右子树存在root-right不为nullptr在str中添加左括号(递归调用tree2str处理右子树并将结果添加到str中最后再添加右括号)。 class Solution {
public:string tree2str(TreeNode* root) {string str ;if(root nullptr) return str;str to_string(root-val);if(root-left) {str (;str tree2str(root-left);str );}else if(root-right){str ();}if(root-right){str (;str tree2str(root-right);str );} return str;}
}; 2. 二叉树的分层遍历1
. - 力扣LeetCode 二叉树的层序遍历多了一个条件把每一层都存放在一个二维动态数组中主要是控制每一层的个数然后放入vector中在把每个vector放入vector的vector中。 层序遍历依靠队列来实现当访问根的时候出根节点然后把该节点的左右节点分别入队记住这里队列存储的是二叉树节点的指针而不是该节点的值这是因为在遍历的过程中需要访问左右子节点。 遍历过程当从队列中取出一个节点的时候通过 front-val 获取该节点的值并存储在临时vector中 class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* q;vectorvectorint vv;if(root)q.push(root);while(!q.empty()) {int levelSize q.size();vectorint v;for(int i 0; i levelSize; i) {TreeNode* front 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;}
}; 3. 二叉树的分层遍历2
. - 力扣LeetCode 该题和二叉树的分层遍历1是一样的只需要把最后的存储在二维动态数组中的值逆序 class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {vectorvectorint vv;queueTreeNode* q;if(root)q.push(root);while(!q.empty()) {vectorint v;int leveSize q.size();for(int i 0; i leveSize; i) {TreeNode* front 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;}
}; 4. 二叉树的最近公共祖先
. - 力扣LeetCode 一、公共祖先的特征总结 当节点 p 是节点 q 的孩子时当前节点就是祖先反之亦然。这是因为在二叉树中如果一个节点是另一个节点的直接子节点那么它们的共同祖先就是父节点。当 p 和 q 分别在当前节点的左右子树中时当前节点就是它们的祖先。这是因为从根节点开始向下遍历只有当两个节点分别位于不同子树时当前节点才是它们的最低公共祖先。 二、情况 1二叉搜索树 条件 a 如果一个节点的值比当前节点小另一个节点的值比当前节点大那么当前节点就是它们的祖先。这是因为二叉搜索树的特性是左子树节点的值小于根节点的值右子树节点的值大于根节点的值。所以当两个节点分别位于当前节点的两侧时当前节点必然是它们的最低公共祖先。例如在一个二叉搜索树中当前节点值为 10p节点值为 5q节点值为 15那么当前节点就是 p 和 q 的最低公共祖先。条件 b 如果两个节点的值都比当前节点小那么递归到左子树中去找祖先。因为二叉搜索树的特性值小的节点必然在左子树中。同理如果两个节点的值都比当前节点大那么递归到右子树中去找祖先。例如当前节点值为 10p 节点值为 5q 节点值为 8那么需要在当前节点的左子树中继续查找它们的最低公共祖先。 三、情况 2三叉链 在三叉链的情况下类似于链表找交点问题。 四、情况 3普通二叉树(该题目对应的情况) 条件 a当一个节点在当前节点的左子树另一个节点在当前节点的右子树时当前节点就是它们的祖先。这与公共祖先的特征一致因为在普通二叉树中没有特定的大小关系只能通过遍历整个树来确定最低公共祖先。例如在一个普通二叉树中当前节点有左子树和右子树p 在左子树中q 在右子树中那么当前节点就是 p 和 q 的最低公共祖先。条件 b 如果两个节点都在左子树递归到左子树中查找如果两个节点都在右子树递归到右子树中查找。这是因为在普通二叉树中没有特定的顺序只能通过逐步遍历子树来确定最低公共祖先。例如当前节点有左子树和右子树p 和 q 都在左子树中那么需要在当前节点的左子树中继续查找它们的最低公共祖先。 方法一 这种方法比较直观先判断节点是否在树中然后再根据节点的位置来确定最低公共祖先 class Solution {
public:bool Find(TreeNode* root,TreeNode* x) {if(root nullptr)return false;return root x || Find(root-left,x) || Find(root-right,x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 1,先看根节点是不是祖先if(root nullptr || root p || root q)return root;bool pInLeft, pInRight, qInLeft, qInRight;pInLeft Find(root-left, p);pInRight !pInLeft;qInLeft Find(root-left,q);qInRight !qInLeft;if((pInLeft qInRight) || (qInLeft pInRight)) return root;if(pInLeft qInLeft) return lowestCommonAncestor(root-left,p,q);if(pInRight qInRight) return lowestCommonAncestor(root-right,p,q);return nullptr;}
}; 方法二 先看根是不是和 p 或者 q 中一个相等如果不是相等 假设在左子树中找到了 p在右子树中找到没有找到右子树这边返回 nullptr 所以左子树这边的值就是最近公共祖先。反之亦然。 如果一个在左边一个在右边都有返回值直接返回根。 class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 1. 先看根节点是不是祖先if (root NULL || root p || root q) return root;// 2. 如果根节点是祖先有没有更近的祖先呢// 看看左子树struct TreeNode* left lowestCommonAncestor(root-left, p, q);// 看看右子树struct TreeNode* right lowestCommonAncestor(root-right, p, q);// 3. 如果有的话显然只会在一侧 判断一下if (left NULL) return right;if (right NULL) return left;// 4. 如果没有更近的默认还是返回rootreturn root;}
};
接下来顺便把二叉搜索树的最近公共祖先这个题目也完成了思路一样
. - 力扣LeetCode
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root nullptr || root p || root q)return root;if ((root-val p-val root-val q-val) || (root-val q-val root-val p-val))return root;if (p-val root-val q-val root-val)return lowestCommonAncestor(root-left, p, q);if (p-val root-val q-val root-val)return lowestCommonAncestor(root-right, p, q);return nullptr;}
}; 5. 将二叉搜索树转换为排序的双向链表
. - 力扣LeetCode 链接中间关系步骤① 二叉搜索树的中序遍历左 - 根 - 右会产生一个有序的节点序列。在converList函数中通过递归实现中序遍历。在遍历过程中当处理每个节点时利用一个引用参数prev来连接节点。例如当prev不为nullptr时prev - right cur和cur - left prev这两个操作就把当前节点cur和之前的节点prev双向连接起来。这样就按照中序遍历的顺序逐步构建了链表的中间部分。找头节点和尾节点步骤② 由于中序遍历的第一个节点是最左节点所以遍历二叉树找到最左节点作为链表的头节点是合理的。从逻辑上来说这个最左节点在二叉搜索树中是值最小的节点。同样在找到头节点后通过不断地沿着节点的右指针移动最终可以找到最右节点它将作为链表的尾节点。返回头节点步骤③ 因为头节点是中序遍历的第一个节点而中序遍历是升序排列节点值的所以这个头节点的值是整个链表也就是原来二叉搜索树中序遍历后的节点序列中的最小值。返回头节点就可以作为整个循环双向链表的起始点方便后续对链表进行操作。 class Solution {
public:void converList(Node* cur, Node* prev) {if(cur nullptr) return;converList(cur-left,prev);if(prev)prev-right cur;cur-left prev;prev cur;converList(cur-right,prev);} Node* treeToDoublyList(Node* root) {Node* prev nullptr;converList(root,prev);Node* head root;while(head head-left)head head-left;if(head nullptr)return head;Node* tail head;while(tail tail-right) tail tail-right;head-left tail;tail-right head;return head;}
}; 6. 从前序与中序遍历序列构造二叉树
. - 力扣LeetCode 这个题目理解起来有一点抽象画图结合代码理解就可以了。 一、解题关键 前序遍历的特点是先访问根节点然后是左子树最后是右子树。所以前序遍历结果中的第一个元素一定是整棵树的根节点。中序遍历的特点是先访问左子树然后是根节点最后是右子树。通过在中序遍历中找到根节点的位置可以确定左子树和右子树的元素范围。 二、构建步骤 首先从前往后取前序遍历结果中的第一个元素创建一个新的节点作为当前子树的根节点。然后在中序遍历结果中找到这个根节点的值以确定左子树和右子树的范围。 在中序遍历中根节点左边的元素构成左子树右边的元素构成右子树。接着对于左子树 根据确定的左子树范围在前序遍历结果中找到对应左子树的起始位置在前序遍历中根节点后面的一段连续元素是左子树的前序遍历结果。递归调用构建函数传入左子树的前序遍历和中序遍历结果以及对应的范围构建左子树并将构建好的左子树连接到根节点的left指针上。对于右子树 类似地确定右子树在前序遍历中的起始位置在前序遍历中左子树部分之后的连续元素是右子树的前序遍历结果。递归调用构建函数传入右子树的前序遍历和中序遍历结果以及对应的范围构建右子树并将构建好的右子树连接到根节点的right指针上。重复以上步骤直到所有子树都构建完成。 class Solution {
public:TreeNode* _buildTree(vectorint preorder,vectorint inorder,int prei,int inbegin,int inend){if(inbegin inend)return nullptr;TreeNode* root new TreeNode(preorder[prei]);int rooti inbegin;while(rooti inend){if(preorder[prei] inorder[rooti])break;else rooti;}// [inbein,rooi-1] rooti [rooti1,inend]if(inbegin rooti-1)root-left _buildTree(preorder,inorder, prei,inbegin,rooti-1);elseroot-left nullptr;if(rooti 1 inend) root-right _buildTree(preorder,inorder, prei,rooti1,inend);elseroot-right nullptr;return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int prei 0;int inbegin 0, inend inorder.size()-1;return _buildTree(preorder,inorder,prei,inbegin,inend);}
}; 7. 从中序与后序遍历序列构造二叉树
. - 力扣LeetCode 注意点 中序和后序遍历构建二叉树的情况 在通过中序和后序遍历构建二叉树时后序遍历的顺序是 “左 - 右 - 根”。当构建右子树时--end操作是为了更新后序遍历的索引使其指向右子树的最后一个节点在构建右子树的递归调用中。因为后序遍历的特性一旦处理完根节点也就是当前正在构建的节点下一个节点要么是右子树的根节点如果有右子树要么是左子树的根节点如果没有右子树。在构建右子树后end已经指向了左子树的最后一个节点不需要额外的--end操作就可以正确地开始构建左子树。中序和前序遍历构建二叉树的情况推测你这里的prev是类似prei用于前序遍历索引 前序遍历的顺序是 “根 - 左 - 右”。在构建二叉树的递归过程中每次构建一个子树时需要先处理根节点然后是左子树最后是右子树。当构建左子树时prei操作是为了将索引移动到左子树的根节点在前序遍历序列中。而在构建右子树时同样需要prei操作来将索引移动到右子树的根节点因为前序遍历序列中左子树节点之后才是右子树节点。这是由于前序遍历的顺序决定的需要不断更新索引来按照正确的顺序获取子树的根节点。 class Solution {
public:TreeNode* _buildTree(vectorint inorder, vectorint postorder, int end, int inbegin, int inend) {if (inbegin inend) return nullptr;TreeNode* root new TreeNode(postorder[end]);int rooti inbegin;while (rooti inend) {if (inorder[rooti] postorder[end]) break;else rooti;}root-right _buildTree(inorder, postorder, --end, rooti 1, inend);root-left _buildTree(inorder, postorder, end, inbegin, rooti - 1);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {int end postorder.size() - 1;return _buildTree(inorder, postorder, end, 0, inorder.size() - 1);}
};8. 二叉树的前序遍历非递归迭代实现
. - 力扣LeetCode 一、递归写法 class Solution
{
public:void _preorderTraversal(TreeNode* root, vectorint v) {if(root nullptr)return;v.push_back(root-val);_preorderTraversal(root-left,v);_preorderTraversal(root-right,v);}vectorint preorderTraversal(TreeNode* root) {vectorint ret;_preorderTraversal(root,ret);return ret;}
}; 二、非递归写法 整体过程 创建一个空的结果向量ret用于存储遍历结果。创建一个栈st用于辅助遍历。使用一个指针cur指向当前正在处理的节点。进入循环只要当前节点不为空或者栈不为空就继续循环。 第一个内部while循环用于遍历左子树 只要当前节点cur不为空就将其值加入结果 ret表示访问了该节点先访问根节点。将当前节点压入栈中为后续访问右子树做准备。将当前节点指向其左子树继续遍历左子树。当左子树遍历完后当前节点cur为空此时从栈中弹出一个节点top这个节点是上一个被访问的节点的父节点。将当前节点cur指向弹出节点的右子树进行下一轮循环开始遍历右子树。 class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint ret;stackTreeNode* st;TreeNode * cur root;while(cur || !st.empty()) {//1、先访问树的左路节点//2、再访问左路节点的左子树while(cur){ret.push_back(cur-val);st.push(cur); //为了访问右子树cur cur-left;}//取栈中的左路节点的右子树出来访问TreeNode* top st.top();st.pop(); cur top-right; //迭代}return ret;}
}; 9. 二叉树的中序遍历非递归迭代实现
. - 力扣LeetCode 与前序遍历类似就存在一些细微的不同就是访问顺序。(唯一变化的就是访问节点的时机) 左路节点先不访问只入栈然后访问根再访问左路节点的右子树。 右子树通过迭代的方式再分成左路节点和左路节点的右子树的方式访问。 1、左路节点(入栈) 2、取栈中的节点(访问节点访问节点的右子树) class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint ret;stackTreeNode* st;TreeNode* cur root;while(cur || !st.empty()) {//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 ret;}
}; 10. 二叉树的后序遍历非递归迭代实现
. - 力扣LeetCode 还是一样的只不过访问的时机不一样 左路节点的访问所以还需要加一个条件右为空可以访问右访问过了也可以访问 通过一个指针 lastNode 记录上一次访问的节点以确定何时处理当前节点。如果不加这个指针处理就是重复拿到栈中的左路节点的值 class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint ret;TreeNode* cur root;TreeNode* lastNode nullptr;stackTreeNode* st;while(cur || !st.empty()) {while(cur) {st.push(cur);cur cur-left;}TreeNode* top st.top();if(top-right nullptr || lastNode top-right) {ret.push_back(top-val);lastNode top;st.pop();} else {cur top-right;}}return ret;}
};
