连锁租车网站源码,建设品牌型网站,汕头多语种网站制作,江西萍乡做网站公司1、先序#xff0c;中序遍历确定二叉树
105
方法一、
前提
① 必须不能有重复元素② 只有先序#xff0b;中序和后序#xff0b;中序才能实现唯一树
思考要点#xff1a;
不要想着用for循环#xff0c;递归一定更好解决输入是vector#xff0c;递归就得考虑传入索…1、先序中序遍历确定二叉树
105
方法一、
前提
① 必须不能有重复元素② 只有先序中序和后序中序才能实现唯一树
思考要点
不要想着用for循环递归一定更好解决输入是vector递归就得考虑传入索引 class Solution {
public: // 辅助函数构建子树 TreeNode* build_subTree(vectorint preorder, unordered_mapint, int inorder_map, int pre_st, int in_st, int in_end) { // 如果当前中序遍历的起始位置大于结束位置返回空指针 if (in_st in_end) return nullptr; // 创建根节点使用前序遍历数组中的当前元素 TreeNode* root new TreeNode(preorder[pre_st]); // 获取当前根节点在中序遍历中的索引 int inorderRootIndex inorder_map[preorder[pre_st]]; // 递归构建左子树 root-left build_subTree(preorder, inorder_map, pre_st 1, in_st, inorderRootIndex - 1); // 递归构建右子树 root-right build_subTree(preorder, inorder_map, pre_st (inorderRootIndex - in_st) 1, inorderRootIndex 1, in_end); // 返回构建好的子树根节点 return root; } // 主函数构建二叉树 TreeNode* buildTree(vectorint preorder, vectorint inorder) { // 创建一个哈希表用于快速查找中序遍历中每个值的索引 unordered_mapint, int inorder_map; for (int i 0; i inorder.size(); i) { inorder_map[inorder[i]] i; // 存储每个节点值到其索引的映射 } // 调用辅助函数构建树初始始点为0结束点为中序遍历的最后一个索引 return build_subTree(preorder, inorder_map, 0, 0, inorder.size() - 1); }
}; 2、中序后序确定二叉树 和上文的思路相似。
/** * Definition for a binary tree node. * struct TreeNode { * int val; // 节点的值 * TreeNode *left; // 左子树的指针 * TreeNode *right; // 右子树的指针 * TreeNode() : val(0), left(nullptr), right(nullptr) {} // 默认构造函数 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 带值构造函数 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} // 带值和左右子树构造函数 * }; */
class Solution {
public: // 递归构建子树的辅助函数 TreeNode* buildsubtree(vectorint postorder, unordered_mapint,int inorder_map, int post_end, int in_st, int in_end) { if (in_st in_end) return nullptr; // 如果当前子树的中序范围无效返回空指针 TreeNode* root new TreeNode(postorder[post_end]); // 取后序遍历最后一个元素作为当前子树的根节点 int inorder_root_index inorder_map[postorder[post_end]]; // 找到根节点在中序遍历中的索引 root-right buildsubtree(postorder, inorder_map, post_end - 1, inorder_root_index 1, in_end); // 递归构建右子树 root-left buildsubtree(postorder, inorder_map, post_end - (in_end - inorder_root_index) - 1, in_st, inorder_root_index - 1); // 递归构建左子树 return root; // 返回当前构建的根节点 } // 主函数接受中序和后序遍历数组并返回构建的二叉树 TreeNode* buildTree(vectorint inorder, vectorint postorder) { unordered_mapint,int inorder_map; // 用于存储中序遍历的元素及其索引 int len postorder.size(); // 获取后序遍历数组的长度 for (auto i 0; i inorder.size(); i) { inorder_map[inorder[i]] i; // 每个元素的值和对应的索引 } return buildsubtree(postorder, inorder_map, len - 1, 0, len - 1); // 调用辅助函数从后序数组的最后一个元素开始构建树 }
};有相同点
均为分左右子树各自递归。map都是由中序遍历来担任。只不过前序找根节点是从前往后后序则是从后往前。
不同点 前序是先构造左子树 后序是先构造右子树。
root-right buildsubtree(postorder, inorder_map, post_end - 1, inorder_root_index 1, in_end); // 递归构建右子树
root-left buildsubtree(postorder, inorder_map, post_end - (in_end - inorder_root_index) - 1, in_st, inorder_root_index - 1); // 递归构建左子树 3、二叉树展开为链表
114
二叉树展开成为链表
114
方法一、
用先序遍历方法将树读出先这里要掌握先序读取树其中就要应用到引用不然递归会爆内存然后再进行建树
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void front_read(TreeNode*root, queueint next_one){if(rootnullptr)return;next_one.push(root-val);front_read(root-left,next_one);front_read(root-right,next_one);}void build_tree(TreeNode*root,queueintfront_num){if(front_num.size()0){TreeNode* right_son new TreeNode(front_num.front());root-rightright_son;front_num.pop();build_tree(root-right,front_num);}}void flatten(TreeNode* root) {if(rootnullptr)return;queueint front_num;front_read(root,front_num);root-leftnullptr;front_num.pop(); // 记得要把第一个去掉噢build_tree(root,front_num);}
};
