从化区住房和建设局网站,做水果网站用什么域名,郑州app外包公司,广州手工外发加工网1 题目
用递归的方法对给定的二叉树进行后序遍历。
例如#xff1a;
给定的二叉树为{1,#,2,3}, 返回[3,2,1].
示例1
输入
{1,#,2,3}
输出
[3,2,1]
2 解法
2.1 递归解法
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/c…1 题目
用递归的方法对给定的二叉树进行后序遍历。
例如
给定的二叉树为{1,#,2,3}, 返回[3,2,1].
示例1
输入
{1,#,2,3}
输出
[3,2,1]
2 解法
2.1 递归解法
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/class Solution {
public:/*** * param root TreeNode类 * return int整型vector*/vectorint postorderTraversal(TreeNode* root) {// write code herevectorint res;if (root nullptr)return res;if (root-left ! nullptr) {vectorint left_res postorderTraversal(root-left);for (int i 0; i left_res.size(); i) {res.push_back(left_res[i]);}}if (root-right ! nullptr) {vectorint right_res postorderTraversal(root-right);for (int i 0; i right_res.size(); i) {res.push_back(right_res[i]);}}res.push_back(root-val);return res;}
};
性能还可以: 2.2 非递归解法
后续遍历,首先是遍历左节点,然后是右节点,最后是自身,所以可以通过栈的方式,放入自身,然后放右节点,最后是左节点,然后检查栈顶,如果是叶子节点,那么遍历,出栈.如果发现其有左/右子节点,不可以直接把左/右子节点入栈(因为左右子节点遍历过了之后继续入栈会陷入死循环), 要先检查一下,设置一个标记前一个出栈节点的标记指针,如果这个前一个出栈节点不是自己的左右子节点(且不能为空),那么说明他的左右子节点还没有遍历过,那么左右子节点入栈,否则遍历自身且出栈:
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/class Solution {
public:/*** * param root TreeNode类 * return int整型vector*/vectorint postorderTraversal(TreeNode* root) {// write code herevectorint res;if (root ! nullptr) {stackTreeNode* tS;tS.push(root);TreeNode* pre nullptr;while(!tS.empty()) {TreeNode* tN tS.top();if ((tN-left nullptr tN-right nullptr) ||(pre ! nullptr (pre tN-left || pre tN-right))) {res.push_back(tN-val);tS.pop();pre tN;} else {if (tN-right ! nullptr)tS.push(tN-right);if (tN-left ! nullptr)tS.push(tN-left);}}}return res;}
};
