LintCode-68.二叉树的后序遍历

二叉树的后序遍历

给出一棵二叉树，返回其节点值的后序遍历。

样例

给出一棵二叉树 {1,#,2,3},

返回 [3,2,1]

挑战

你能使用非递归实现么？

标签

递归二叉树二叉树遍历

code

/**

 * Definition of TreeNode:

 * class TreeNode {

 * public:

 *     int val;

 *     TreeNode *left, *right;

 *     TreeNode(int val) {

 *         this->val = val;

 *         this->left = this->right = NULL;

 *     }

 * }

 */

class Solution {

    /**

     * @param root: The root of binary tree.

     * @return: Postorder in vector which contains node values.

     */

public:

    vector<int> postorderTraversal(TreeNode *root) {

        // write your code here

        vector<int> order;

        if(root == NULL)

            return order;

        stack<TreeNode*> s;

        TreeNode *cur;                      //当前结点

        TreeNode *pre=NULL;                 //前一次访问的结点

        s.push(root);

        while(!s.empty()) {

            cur=s.top();

            //如果当前结点没有孩子结点或者孩子节点都已被访问过

            if((cur->left==NULL&&cur->right==NULL)|| (pre!=NULL&&(pre==cur->left||pre==cur->right))) {

                order.push_back(cur->val);

                s.pop();

                pre=cur;

            }

            else {

                if(cur->right!=NULL)

                    s.push(cur->right);

                if(cur->left!=NULL)

                    s.push(cur->left);

            }

        }

        return order;

    }

};

巴特西

LintCode-68.二叉树的后序遍历

二叉树的后序遍历

样例

挑战

标签

code

最新文章

热门文章