给出一棵二叉树，返回其节点值的后序遍历。
样例 1:
输入：{1,2,3} 输出：[2,3,1] 解释： 1 / \ 2 3 它将被序列化为{1,2,3} 后序遍历样例 2:
输入：{1,#,2,3} 输出：[3,2,1] 解释： 1 \ 2 / 3 它将被序列化为{1,#,2,3} 后序遍历python：
""" Definition of TreeNode: class TreeNode: def __init__(self, val): self.val = val self.left, self.right = None, None """ class Solution: """ @param root: A Tree @return: Postorder in ArrayList which contains node values. """ def postorderTraversal(self, root): # write your code here endnode = False node = [root] result = [] if root == None: return result while not endnode: while root.left != None or root.right != None: if root.left != None: node.append(root) root = root.left else: node.append(root) root = root.right supnode = node[-1] while root == supnode.right or supnode.right == None: result.append(root.val) del node[-1] if len(node) == 1: result.append(supnode.val) endnode = True break root = supnode supnode = node[-1] if root == supnode.left and supnode.right != None: result.append(root.val) root = supnode.right return result
C++：
/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: A Tree * @return: Postorder in ArrayList which contains node values. */ vector<int> postorderTraversal(TreeNode * root) { // write your code here vector<int> result; if(root == NULL) { return result; } vector<TreeNode*> node; TreeNode * temp = root; bool endnode = false; while(!endnode) { while(root->left != NULL || root->right != NULL) { if(root->left != NULL) { node.push_back(root); root = root->left; }else{ node.push_back(root); root = root->right; } } TreeNode *supnode = node.back(); while(root == supnode->right || supnode->right == NULL) { result.push_back(root->val); node.pop_back(); if(node.size() == 0) { result.push_back(supnode->val); endnode = true; break; } root = supnode; supnode = node.back(); } if(root == supnode->left && supnode->right != NULL) { result.push_back(root->val); root = supnode->right; } } return result; } };
PS：后序最难写，因为要判断节点在左支还是右支
