首页 > 代码库 > Binary Tree Postorder Traversal

Binary Tree Postorder Traversal

2024-07-16 21:38:59   220人阅读

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?

思路：使用tag标记元素的左右子树是否已经输出完毕。若是，则输出该元素并将其出栈；否则，先遍历其左子树再遍历其右子树，同时修改tag值。

 1 class StackNode 2 { 3  public: 4     StackNode():tag(true),node(0){} 5     StackNode( short aTag, TreeNode *aNode ):tag(aTag),node(aNode){} 6     short tag; 7     TreeNode *node; 8 }; 9 10 class Solution {11 public:12     vector<int> postorderTraversal(TreeNode *root) {13         vector<int> values;14         list<StackNode> stack;15         // root is empty.16         if( root == 0 ) { return values; }17         stack.push_back( StackNode( 1, root ) );18         19         // main loop.20         while( !stack.empty() ) {21             StackNode& sNode = stack.back();22             if( sNode.tag == 1 ) { // need to access left child.23                 sNode.tag = 2;24                 if( sNode.node->left ) {25                     stack.push_back( StackNode( 1, sNode.node->left ) );26                 }27             }28             else if( sNode.tag == 2 ) { // need to access right child.29                 sNode.tag = 3;30                 if( sNode.node->right ) {31                     stack.push_back( StackNode( 1, sNode.node->right ) );32                 }33             }34             else { // access current value.35                 values.push_back( sNode.node->val );36                 stack.pop_back();37             }38         }39         return values;40     }41 };

以下是网上看到的更加简洁的代码：（若上一个输出的元素是当前节点的左儿子或者右儿子，则说明已经完成了对其左右子树的遍历，输出当前节点并将其出栈；否则，将其左右儿子分别入栈。）

 1 class Solution { 2 public: 3     vector<int> postorderTraversal(TreeNode *root) { 4         vector<int> ans; 5         list<TreeNode*> node_list; 6         if(root == NULL) return ans; 7         node_list.push_front(root); 8         TreeNode *head = root; 9         while(!node_list.empty())10         {11             TreeNode *cur = node_list.front();12             13             if(cur -> right == head || cur -> left == head || ((cur -> right == NULL) && (cur -> left == NULL)))14             {15                 node_list.pop_front();16                 ans.push_back(cur -> val);17                 head = cur;18             }19             else20             {21                 if(cur -> right != NULL) node_list.push_front(cur -> right);22                 if(cur -> left != NULL) node_list.push_front(cur -> left);23             }24         }25     }26 };

 


联系
我们