145. Binary Tree Postorder Traversal

发表于 | 分类于 | 浏览 次

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

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

非递归解法

在遍历一个节点之前，以该节点为根的子树应该已经遍历完了。也就是说，如果一棵树的左子树未被遍历，则应该先遍历左子树，然后遍历右子树。根据这样的遍历顺序可知，在遍历序列中，左孩子在右孩子前面，右孩子在根前面。如果遍历到一个节点时，上一个遍历到的节点不是它的左孩子(当该节点的右孩子为空)，就是它的左孩子(该节点的左子树不为空)，或者其他节点(当该节点是叶子节点)。如果上一个被遍历的节点既不是该节点的左孩子也不是该节点的右孩子，且该节点不是叶子节点，那么说明该节点的左子树尚未被遍历，因此，先将左孩子加入到栈中。

如果上一个被遍历的节点是该节点的左孩子，那么说明该节点的左子树已经遍历完了。如果该节点的左子树为空，那么上一个被遍历的节点为其他节点。所以，当一个节点存在右孩子，且上一个被遍历的节点不是右孩子时，说明该节点的右子树尚未被遍历。因此，将右孩子加入到栈中。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * 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) {
        if(root == nullptr){
            return {};
        }
        stack<TreeNode*> st;
        vector<int> res;
        TreeNode* cur;
        TreeNode* last = root;
        st.push(root);
        while(!st.empty()){
            cur = st.top();
            
            /* 如果该节点有左孩子且上一个遍历的节点不是左孩子也不是右孩子时 
             * 如果该节点的左右子树都已经被遍历，
             *		如果右子树不为空，上一个被遍历的节点应该是右孩子
             *     如果右子树为空，上一个被遍历的节点为左孩子
             */
            
            if(cur->left != nullptr && cur->left != last && cur->right != last){
                st.push(cur->left);
            }else if(cur->right != nullptr &&  cur->right != last){
                st.push(cur->right);
            }else{
                res.push_back(cur->val);
                last = cur;
                st.pop();
            }
        }
        return res;
    }
};