东莞网站推广哪些,项目外包流程,做外汇网站,外国手表网站题目
给你一棵二叉树的根节点 root #xff0c;返回其节点值的 后序遍历 。
示例 1#xff1a; 输入#xff1a;root [1,null,2,3]
输出#xff1a;[3,2,1]
示例 2#xff1a;
输入#xff1a;root []
输出#xff1a;[]示例 3#xff1a;
输入#xff1a;root…题目
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。
示例 1 输入root [1,null,2,3]
输出[3,2,1]
示例 2
输入root []
输出[]示例 3
输入root [1]
输出[1]
进阶递归算法很简单你可以通过迭代算法完成吗 方法一普通递归写法
/*** 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 istree(TreeNode* root,vectorint arr2){if(rootnullptr)return;istree(root-left,arr2);//先遍历左子树istree(root-right,arr2);//遍历右子树arr2.push_back(root-val);//保存当前节点的值return;}vectorint postorderTraversal(TreeNode* root) {vectorint arr1;istree(root,arr1);return arr1;}
};方法二通过栈实现非递归迭代
/*** 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:vectorint postorderTraversal(TreeNode* root) {vectorint arr1;stackTreeNode* st;TreeNode* curroot;TreeNode* prev;while(cur||!st.empty())//cur不为空或栈里还有节点就继续{while(cur)//找左路并push直到找到最左节点{st.push(cur);curcur-left;}TreeNode* topst.top();//保存最左节点//如果右为空或者prev和该节点右子节点相等说明右边已经访问过了可以popif(top-rightnullptr||prevtop-right){st.pop();prevtop;//记录此次访问节点地址为下一次做参考arr1.push_back(top-val);}else{curtop-right;}}return arr1;}
};
