LeetCode Binary Tree Postorder Traversal

1.题目

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?

2.解决方案1

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res; 
        if(root == NULL){
            return res;
        }
        stack<TreeNode*> stackNode;
        stackNode.push(root);
        TreeNode* preNode = NULL;
        while(stackNode.empty() == false){
            TreeNode* curNode = stackNode.top();

            bool isLeafNode = curNode->left == NULL && curNode->right == NULL;
            if(isLeafNode || (preNode != NULL && (preNode == curNode->left || preNode == curNode->right))){
                res.push_back(curNode->val);
                stackNode.pop();
                preNode = curNode;
            }else{
                if(curNode->right != NULL){
                    stackNode.push(curNode->right);
                }
                if(curNode->left != NULL){
                   stackNode.push(curNode->left);
                }
            }

        }
        return res;
    }
};

思路：非递归的方式要用stack来辅助。

关键点1：

我们知道stack是先进的后出，而后序遍历是要先访问左节点，所以我们要先把右节点push到stack中，再push左节点。

关键点2：

叶子可以直接输出了，但如果一个节点有左右一个节点，也是要输出的，输出的时机是这题的难点。这里又增加了一个变量，来记录之前输出的点，假如一个节点的左右叶子节点有一个输出了，然后再访问到这个节点，因为stack的特性，说明左右节点都已经输出了，说明这个时候就可以输出这个根节点了。

3.解决方案2

class Solution {
public:
    vector<int> result;

    void HXBL(TreeNode* root){
        if(root == nullptr)
		return;

        if(root->left != NULL){
            HXBL(root->left);
        }
        if(root->right != NULL){
            HXBL(root->right);
        }
        if(root != NULL){
            result.push_back(root->val);
        }

    }

    vector<int> postorderTraversal(TreeNode *root) {
        result.clear();
        HXBL(root);
        return result;
    }
};

递归当然简单了，就是慢。慢就是bug。

http://www.waitingfy.com/archives/1608

数据结构 & 算法 | RSS 2.0 |