leetcode:binary-tree-postorder-traversal-白红宇

leetcode:binary-tree-postorder-traversal

阅读量：4180 次

发布时间：2019-05-26

本文共 1608 字，大约阅读时间需要 5 分钟。

题目描述：树的后序遍历

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].

实现：

1.递归方式

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    void postOrder(TreeNode *root,vector
   
    &vec){        if(root != NULL){//递归实现，比较简单            postOrder(root->left,vec);            postOrder(root->right,vec);            vec.push_back(root->val);        }    }         vector
    
      postorderTraversal(TreeNode *root) {        vector
     
       vec;        postOrder(root,vec);        return vec;    }};

2.非递归方式

需要用栈来保存每次的父节点

class Solution {public:      vector
   
     postorderTraversal(TreeNode *root) {          vector
    
     vec;        if(root == NULL)            return vec;        stack
     
      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;                  }};