首页 > 代码库 > Leetcode Binary Tree Postorder Traversal

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?

vector<int> postorderTraversal(TreeNode *root){    vector<int> res;    if(root == NULL) return res;    stack<TreeNode *> record;    record.push(root);    TreeNode *pre = NULL;    while(!record.empty()){        TreeNode *node = record.top();        if((node->left == NULL  && node->right == NULL)||(pre!=NULL &&(pre == node->left || pre == node->right)) ){            res.push_back(node->val);            record.pop();            pre = node;        }else{            if(node->right) record.push(node->right);            if(node->left ) record.push(node->left);        }        }    return res;}

 另一种方法:

通过不断的交换左右孩子,然后压栈,最后弹出,即可得到结果

时间复杂度为O(h),h为树的高度,空间复杂度为O(n)

vector<int> postorderTraversa(TreeNode *root){    vector<int> res;    if(root == NULL) return res;    stack<TreeNode *> post_record,reverse_record;    post_record.push(root);    while(!post_record.empty()){        TreeNode *node = post_record.top();        reverse_record.push(node);        post_record.pop();        if(node->left) post_record.push(node->left);        if(node->right) post_record.push(node->right);    }    while(!reverse_record.empty()){        res.push_back(reverse_record.top()->val);        reverse_record.pop();    }    return res;}