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] .
창고로 귀속 과정을 시뮬레이션하면 뒷순서는 다른 두 개의 역행 방식보다 약간 복잡하고 좌우 하위 노드가 역행 후 루트에 접근하는 것을 판단해야 한다.
코드:
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        stack<TreeNode*> st;
        vector<int> ret;
        if(root == NULL)
            return ret;
        TreeNode* cur = NULL;
        TreeNode* pre = NULL;
        st.push(root);
        while(!st.empty())
        {
            cur = st.top();
            if((cur->left == NULL && cur->right == NULL) ||
               (pre != NULL && (cur->left == pre || cur->right == pre)))// , 
            {
                ret.push_back(cur->val);
                st.pop();
                pre = cur;
            }
            else
            {
                if(cur->right != NULL)
                    st.push(cur->right);
                if(cur->left != NULL)
                    st.push(cur->left);
            }
        }
        return ret;
        
    }
};

좋은 웹페이지 즐겨찾기