[leetcode] 145. Binary Tree Postorder Traversal

[leetcode] 145. Binary Tree Postorder Traversal

Description

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

Example:

Input: [1,null,2,3] 1 \ 2 / 3Output: [3,2,1]

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

分析一

题目的意思是：实现二叉树的后序遍历

非递归的化，需要用到栈，注意进栈的顺序。如果结点的左右孩子都为空，说明到了叶结点。在遍历左右孩子的时候，我们在加入栈的的同时，要注意置空，不然出栈回溯的时候又会向下遍历

代码一

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector postorderTraversal(TreeNode *root) { stack stack1; vector result; if(!root){ return result; } stack1.push(root); TreeNode* Node=NULL; while(!stack1.empty()){ Node=stack1-(); if(Node->left==NULL&&Node->right==NULL){ result.push_back(Node->val); stack1.pop(); }else{ if(Node->right){ stack1.push(Node->right); Node->right=NULL; } if(Node->left){ stack1.push(Node->left); Node->left=NULL; } } } return result; }};

分析二

这份代码我觉得写得不错，毕竟用了head指针，避免了继续递归，而直接返回。和代码一中的置空的效果一样。

代码二

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector postorderTraversal(TreeNode* root) { vector res; if(!root){ return res; } stack s; s.push(root); TreeNode* head=root; while(!s.empty()){ TreeNode* t=s-(); if((!t->left&&!t->right)||t->left==head||t->right==head){ res.push_back(t->val); s.pop(); head=t; }else{ if(t->right){ s.push(t->right); } if(t->left){ s.push(t->left); } } } return res; }};

分析三

把前序遍历稍稍改一改，前序是中左右，改成中右左遍历，最后反转结果数组就是最终结果了。

代码三（python）

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: if(root is None): return [] stack=[root] res=[] while(stack): node=stack.pop() res.append(node.val) if(node.left): stack.append(node.left) if(node.right): stack.append(node.right) res.reverse() return res

参考文献

​​[编程题]binary-tree-postorder-traversal​​​​[leetcode] postorder​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。