这些小活动你都参加了吗?快来围观一下吧!>>
电子产品世界 » 论坛首页 » 嵌入式开发 » STM32 » binary-tree-postorder-traversa

共1条 1/1 1 跳转至

binary-tree-postorder-traversa

高工
2018-02-01 13:25:40     打赏

Given a binary tree, return thepostorder traversal of its nodes' values.

For example:
Given binary tree{1,#,2,3},

   1
    \
     2
    /
   3


return[3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?


方法一:

(1)前序遍历:根-》左-》右

(2)变成:根-》右-》左

(3)然后逆序


[cpp] view plain copy
  1. class Solution  

  2. {  

  3. public:  

  4.     vector<int> postorderTraversal(TreeNode* root)  

  5.     {  

  6.         vector<int> res;  

  7.         if (!root)  

  8.         {  

  9.             return res;  

  10.         }  

  11.   

  12.         stack<TreeNode*> st;  

  13.         st.push(root);  

  14.           

  15.         while (st.size())  

  16.         {  

  17.             TreeNode* tmp = st.top();  

  18.             st.pop();  

  19.   

  20.             res.push_back(tmp->val);  

  21.             if (tmp->left)  

  22.             {  

  23.                 st.push(tmp->left);  

  24.             }  

  25.             if (tmp->right)  

  26.             {  

  27.                 st.push(tmp->right);  

  28.             }  

  29.         }  

  30.   

  31.         reverse(res.begin(), res.end());  

  32.     }  

  33. };  


方法二:递归实现



[cpp] view plain copy
  1. class Solution  

  2. {  

  3. public:  

  4.     vector<int> postorderTraversal(TreeNode* root)  

  5.     {  

  6.         vector<int> ans;  

  7.         LRD(ans, root);  

  8.         return ans;  

  9.     }  

  10.   

  11.     void LRD(vector<int>&ans, TreeNode* root)  

  12.     {  

  13.         if (root==NULL)  

  14.         {  

  15.             return;  

  16.         }  

  17.   

  18.         LRD(ans, root->left);  

  19.         LRD(ans, root->right);  

  20.         ans.push_back(root->val);  

  21.     }  

  22. }; 




共1条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]