此题来自leetcode https://oj.leetcode.com/problems/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?
非递后续归遍历二叉树，肯定得用到栈。先序遍历很好写，但后续遍历就不是那么容易了。
只需要设置个指针pre，指向最后输出的那个节点就行了，只要判断cur指针指向的是上次输出节点的父节点，且cur无其他未遍历的节点，这个时候就把cur节点输出即可，然后更改pre。原理是要遍历当前节点，其所有子节点都必须遍历完，因为肯定是先左后右，所以只需一个指针保持前一次输出的结果即可。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> postorderTraversal(TreeNode *root) { vector<int> v; if (NULL == root) return v; stack<TreeNode*> s; s.push(root); TreeNode * pre = root; while (!s.empty()) { TreeNode * cur = s.top(); if ((NULL == cur->left && NULL == cur->right) || (pre == cur->left || pre == cur->right)) { s.pop(); v.push_back(cur->val); pre = cur; } else { if (cur->right) s.push(cur->right); if (cur->left) s.push(cur->left); } } return v; } };
