首页 > 代码库 > leetcode -- Binary Tree Postorder Traversal

leetcode -- Binary Tree Postorder Traversal

2024-07-17 14:43:13   223人阅读

历史不容假设

 [问题描述]

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?

非递归实现二叉树后续遍历

[解题思路]

说明：网络上好多相关的方法，但是基本上都使用的O(n)的空间来记录节点是否已经访问过，所以我再次特地列举此题算法，需要O(stack) + O(1) 空间复杂度

如果栈顶元素的孩子节点是刚刚访问过的节点，那么就说明孩子节点已经访问结束，出栈！

 1  std::vector<int> Solution::postorderTraversal(TreeNode *root) 2  { 3      std::vector<int> ans; 4      std::stack<TreeNode*> pathStack; 5      if (root == NULL) 6         return ans; 7      TreeNode *post = root; 8      pathStack.push(root); 9      while (!pathStack.empty()){10         TreeNode* tmp = pathStack.top();11         if (tmp->left == post || tmp->right == post || (tmp->left == NULL && tmp->right == NULL)){12             ans.push_back(tmp->val);13             pathStack.pop();14             post = tmp;15         }16         else{17             if (tmp->right != NULL) pathStack.push(tmp->right);18             if (tmp->left != NULL) pathStack.push(tmp->left);19         }20      }21  }

 


联系
我们