转载

binary-tree-postorder-traversal

binary-tree-postorder-traversal

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

For example:

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?

思想

首先看到二叉树后序遍历,很多人第一眼想到的是递归的方法,但题目强调用非递归的方法

所以可以考虑用栈,应为递归的实质实现还是通过栈

  • 方法一

    1. 根节点入栈
    2. 访问栈顶节点(并不出栈)
    3. 如果栈顶节点左右孩子都为空,出栈,转6,否则进行4,5步
    4. 栈顶节点的右节点入栈(右节点不为空的条件下),栈顶节点的右节点赋值为NULL
    5. 栈顶节点的左节点入栈(左节点不为空的条件下),栈顶节点的左节点赋值为NULL
    6. 重复上述步骤2-5,直到栈为空
  • 方法二

? (方法一,改变了树的结构,方法二可以克服这个缺点,用一个map标记访问次数)

  1. 根节点入栈
  2. 访问栈顶节点(并不出栈)
  3. 如果栈顶节点左右孩子都为空,出栈 转7,否则进行步骤4
  4. 如果栈顶节点是第一次访问,进行步骤5,6,如果栈顶节点是第二次访问,出栈 转7
  5. 栈顶节点的右节点入栈(右节点不为空的条件下)
  6. 栈顶节点的左节点入栈(左节点不为空的条件下)
  7. 重复上述步骤2-6,直到栈为空

方法一代码

class Solution {
public: 
    vector<int> postorderTraversal(TreeNode *root) {     
        vector<int>vec;
        if(root == NULL)
            return vec;
        stack<TreeNode*>st;
        st.push(root);
         
        TreeNode * cur = NULL;
         
        while(!st.empty()){            
            cur = st.top();
            if(cur->left == NULL && cur->right == NULL){
                vec.push_back(cur->val);
                st.pop();
            }else{
                if(cur->right){
                    st.push(cur->right);
                    cur->right = NULL;
                }
                if(cur->left){
                    st.push(cur->left);
                    cur->left = NULL;
                }
            }
        }
        return vec;        
    }
};

方法二代码

#include<vector>
#include<stack>
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> a;
        if(root == NULL) return a;

        stack<TreeNode*> b;
       /*标记访问次数*/
        map<TreeNode*, int>c;
        b.push(root);


        TreeNode *temp;
        while(!b.empty()){
            temp = b.top();
            if(temp->left == NULL && temp->right == NULL) {
                a.push_back(temp->val);
                b.pop();
            }
            else {
                if(c.count(temp) > 0) c[temp]++;
                else c[temp] = 1;

                if(c[temp] == 2) {
                    a.push_back(temp->val);
                    b.pop();
                } 
                else {
                    if(temp->right != NULL) b.push(temp->right);    
                    if(temp->left != NULL) b.push(temp->left);     
                }
            }

        }
        return a; 
    }
};
正文到此结束
本文目录