Given a binary tree, return the?postorder?traversal of its nodes' values.

For example:
Given binary tree?[1,null,2,3],

1\2/3

思路： 借助于一個棧，依次將根節點的右子節點和左子節點壓入棧中。如果一個節點為葉子節點，或者前一個出棧的元素為當前棧頂節點的子節點，則出棧。

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

?

轉載于:https://www.cnblogs.com/zhaoyaxing/p/8502683.html

總結

以上是生活随笔為你收集整理的145. Binary Tree Postorder Traversal的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。