【Leetcode】【hard】Binary Tree Postorder Traversal

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

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

解题：

二叉树的后序遍历，比先序和中序遍历稍显麻烦一些，有兴趣可查看：二叉树先序遍历、二叉树中序遍历

后序遍历需要输出左子树后，输出右子树，最后输出当前结点。复杂的原因是，输出左右子树后，如何判断输出的结点是左还是右。如果左结点已经输出，就继续输出右；如果右结点已经输出，就输出当前结点，并pop出栈中上一层的结点继续考察。因此，后序遍历和先中序遍历代码上主要不同是：

1、引入lastNode指针，指向刚刚输出的结点，方便判断刚刚输出的结点是上一层的左儿子还是右儿子；

2、如果一个结点，连同其左子树和右子树都已经输出完毕，应继续pop栈中元素，但是新pop出的结点，在下一次循环中不应再循环遍历其左子树。

因此在一个结点连同其子树都输出完毕后，将curNode置为0，这样跳过循环头部的“循环查找左子树”过程之后再pop栈中元素，从而直接进入判定阶段。

代码：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> postorderTraversal(TreeNode* root) {
13         TreeNode* curNode = root;
14         TreeNode* lastNode = NULL;
15         stack<TreeNode *> nodes;
16         vector<int> res;
17         
18         while (curNode != NULL || !nodes.empty()) {
19             while (curNode) {
20                 nodes.push(curNode);
21                 curNode = curNode->left;
22             }
23             
24             curNode = nodes.top();
25             if (curNode->right && curNode->right != lastNode) {
26                 curNode = curNode->right;
27             } else {
28                 res.push_back(curNode->val);
29                 lastNode = curNode;
30                 nodes.pop();
31                 curNode = NULL;
32             }
33         }
34         
35         return res;
36     }
37 };

【Leetcode】【hard】Binary Tree Postorder Traversal

推荐阅读