首页 > 代码库 > Binary Tree Postorder Traversal

Binary Tree Postorder Traversal

2024-07-01 23:49:20   216人阅读

Problem:

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

For example:

Given binary tree {1, #, 2, 3},

return [3, 2, 1]

Note: Recursive solution is trivial, could you do it iteratively?

分析：

后序遍历的访问顺序是“左右中”，先遍历左子树、右子树，后遍历根节点。思路基本与先序遍历一致，需要借助堆栈。但是根节点是最后遍历的，所以遍历左子树、右子树时候，只做压栈的操作，不将节点加入遍历序列中。将节点加入遍历序列的条件是当前判断的栈顶的元素，没有右子树，或者右子树的根节点是其前驱（代码的第14行）。将根节点访问完后才将其弹出堆栈（代码的第16行）。

 1 class Solution {
 2 public:
 3     vector<int> postorderTraversal(TreeNode *root) {
 4         vector<int> result;
 5         stack<TreeNode *> stk;
 6         TreeNode *p = root;
 7         while(p != NULL) {
 8             stk.push(p);
 9             p = p->left;
10         }
11         
12         while(!stk.empty()) {
13             TreeNode *top = stk.top();
14             if(top->right == NULL || result.size() > 0 && top->right->val == result.back()) {
15                 result.push_back(top->val);
16                 stk.pop();
17             } else {
18                 TreeNode *p = top->right;
19                 while(p != NULL) {
20                     stk.push(p);
21                     p = p->left;
22                 }
23             }
24         }
25         return result;
26     }
27 };

 


联系
我们