手机微信官方网站首页,做网站需要哪些程序员,做网站的时候怎么照片路径,app界面设计模板素材免费目录 226、翻转二叉树题目描述思路代码 589、N叉树的前序遍历题目描述思路代码 590、N叉树的后序遍历题目描述思路代码 思考总结 226、翻转二叉树
题目描述
给你一棵二叉树的根节点 root #xff0c;翻转这棵二叉树#xff0c;并返回其根节点。 示例#xff1a; 输入… 目录 226、翻转二叉树题目描述思路代码 589、N叉树的前序遍历题目描述思路代码 590、N叉树的后序遍历题目描述思路代码 思考总结 226、翻转二叉树
题目描述
给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 示例 输入root [4,2,7,1,3,6,9] 输出[4,7,2,9,6,3,1]
思路
题目分析只需要把每个节点的左右孩子交换一下就可以实现整体翻转的效果。解法在遍历过程中把每个遍历到的节点的左右孩子进行交换。
代码
1.层序遍历
class Solution {
public:TreeNode* invertTree(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);while (!que.empty()) {int size que.size();for (int i 0; i size; i) {TreeNode* node que.front();que.pop();TreeNode* tempNode node - left;node - left node - right;node - right tempNode;if (node - left) que.push(node - left);if (node - right) que.push(node - right);}}return root;}
};2.前序遍历(递归法) 递归函数的参数和返回值当前节点的指针、返回root节点的指针终止条件参数代表的当前节点为空时终止递归逻辑前序遍历顺序为中左右因此先翻转节点、向左递归、向右递归。 class Solution {
public://参数root代表当前节点TreeNode* invertTree(TreeNode* root) {if (root NULL) return root;//终止条件swap(root - left, root - right);//中invertTree(root - left);//左invertTree(root - right);//右 return root;//返回值}
};3.前序遍历(迭代法)
class Solution {
public://参数root代表当前节点TreeNode* invertTree(TreeNode* root) {stackTreeNode* st;if (root ! NULL) st.push(root);while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();if (node - right) st.push(node - right);//右if (node - left) st.push(node - left);//左st.push(node);//中st.push(NULL);//标记} else {st.pop();//先取出标记node st.top();//中st.pop();swap(node - left, node - right);//翻转}}return root;}
};589、N叉树的前序遍历
题目描述
给定一个 n 叉树的根节点 root 返回 其节点值的 前序遍历 。 n 叉树 在输入中按层序遍历进行序列化表示每组子节点由空值 null 分隔请参见示例。 示例 输入root [1,null,3,2,4,null,5,6] 输出[1,3,5,6,2,4]
思路
1.递归法 返回值无参数cur指向当前节点的指针、终止条件cur为NULL时递归逻辑前序遍历中左右 2.迭代法 每次遍历到一个节点先把这个节点的值加入结果集。为了确保下一个遍历到的节点每次都是当前节点从左到右第一个子节点把当前节点的所有子节点从右到左压入栈中。这样每次从栈顶取出元素都能确保是按照前序遍历的顺序。 代码
1.递归法
class Solution {
public://递归函数//参数cur指向当前节点; res结果集void helper(Node* cur,vectorint res) {if (cur NULL) return;//终止条件res.push_back(cur - val);//中//递归逻辑先顺着每个节点的靠左的子节点递归for (Node* ch : cur - children) {helper(ch, res);}}vectorint preorder(Node* root) {vectorint res;//结果集helper(root, res);return res;}
};2.迭代法
class Solution {
public:vectorint preorder(Node* root) {vectorint res;if (root NULL) return res;stackNode* st;st.push(root);while (!st.empty()) {Node* node st.top();st.pop();res.push_back(node - val);for (int i node - children.size() - 1; i 0; i--) {st.push(node - children[i]);//把当前节点的所有子节点从右到左放入栈中}}return res;}
};590、N叉树的后序遍历
题目描述
给定一个 n 叉树的根节点 root 返回 其节点值的 后序遍历 。 n 叉树 在输入中按层序遍历进行序列化表示每组子节点由空值 null 分隔请参见示例。 示例 输入root [1,null,3,2,4,null,5,6] 输出[5,6,3,2,4,1]
思路
1.递归法 返回值无参数cur当前节点、res结果集终止条件当前节点cur为NULL时递归逻辑左右中先通过递归到最底层的最左边的节点然后开始把节点值加入结果集。 2.迭代法 按照上面前序遍历的模板把子节点压入栈的顺序颠倒一下(从右到左压入栈变成从左到右压入栈)那么最终结果集中的顺序为中右左。在把结果集翻转一下顺序就变成了左右中为后序遍历的顺序。 代码
1. 递归法
class Solution {
public://递归函数//参数cur当前节点、res结果集void helper(Node* cur, vectorint res) {if (cur NULL) return;//终止条件for (Node* ch : cur - children) {helper(ch, res);}res.push_back(cur - val);//中}vectorint postorder(Node* root) {vectorint res;helper(root,res);return res;}
};2.迭代法
class Solution {
public:vectorint postorder(Node* root) {vectorint res;stackNode* st;if (root ! NULL) st.push(root);while (!st.empty()) {Node* node st.top();st.pop();res.push_back(node - val);//中for (Node* ch : node - children) {st.push(ch);//把当前节点的所有子节点从左到右压入栈中}}reverse(res.begin(), res.end());//将结果集翻转return res;}
};思考总结 树的操作都要在遍历的基础上在遍历的过程中添加某些操作。二叉树节点定义 struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL)};创建二叉树节点时要用new TreeNode(num) 3. 递归三要素确定参数和返回值、确定终止条件、确定递归逻辑 4. 树的迭代遍历深度优先遍历离不开栈、广度优先遍历离不开队列
