閱讀181 返回首頁    go 阿裏雲 go 技術社區[雲棲]

LeetCode題目詳解——Binary Tree Postorder Traversal

 

Given a binary tree, return the postorder 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?

後序遍曆比先序和中序遍曆要複雜一些，因為一個節點必須要它的左子樹和右子樹都被遍曆之後才能被訪問。所以被壓入棧的元素重新被訪問到的時候（即此時該元素位於棧頂），必須要判斷該節點的左右子樹是不是已經被遍曆過，如果左右子樹都已經被遍曆，那麼訪問該元素，然後出棧。接著再處理新的棧頂；否則則將該節點的左右子樹壓入棧。具體代碼如下：

class Solution {//應該是最優化的實現方法
    //每次從棧中取出一個節點，通過判斷當前節點是否可以結束訪問。如果可以則將其對應的值放到vector中，並從棧中取出下一個要訪問的節點；如果不可以則將其右左節點分別壓入棧中
public:
    vector<int> postorderTraversal(TreeNode *root) {
        stack<TreeNode*> rest;
        vector<int> result;
        rest.push(root);
        TreeNode *cur,*pre;
        if(root == NULL)
            return result;
        while(!rest.empty())
        {
            cur = rest.top();
            if((cur->left==NULL && cur->right==NULL) || (pre!=NULL)&&(pre==cur->left)||(pre==cur->right))//當前節點可以結束訪問的條件：1、沒有子樹；2、前一個被訪問的節點為當前節點的子樹
            {
                result.push_back(cur->val);
                pre = cur;
                rest.pop();
            }
            else
            {
                if(cur->right)
                    rest.push(cur->right);
                if(cur->left)
                    rest.push(cur->left);
            }
        }
    }
};


最後更新：2017-04-03 05:39:54

  上一篇：go poj 2328 Guessing Game
  下一篇：go C#獲取當前路徑方法