本文主要是介绍【LeetCode】145. 二叉树的后序遍历 [ 左子树 右子树 根结点]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
文章目录
- Python3
- C++
Python3
方法一： 递归 ⟮ O ( n ) ⟯ \lgroup O(n) \rgroup ⟮O(n)⟯
# 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 = right
class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:"""后序遍历 [ 左子树 右子树 根结点 ] 递归 """def postorder(node):if not node:return postorder(node.left) # 左子树 postorder(node.right) # 右子树ans.append(node.val) # 根结点ans = []postorder(root)return ans
方法二： 迭代 ⟮ O ( n ) ⟯ \lgroup O(n) \rgroup ⟮O(n)⟯
# 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 = right
class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:"""后序遍历 [左子树 右子树 根] 迭代"""ans = []stack = []cur = rootpre = Nonewhile cur or stack:while cur:stack.append(cur)cur = cur.left # 左cur = stack.pop()if not cur.right or cur.right == pre: ## 右边 已遍历完ans.append(cur.val) # 根 pre = cur cur = None else:stack.append(cur)cur = cur.right # 右return ans
方法三： Morris ⟮ O ( n ) 、 O ( 1 ) ⟯ \lgroup O(n)、O(1) \rgroup ⟮O(n)、O(1)⟯
写法一
# 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 = right
class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:""" 后序遍历 [ 左子树 右子树 根 ] Morris O(N) O(1)"""### 写法一 根 右 左 反转结果列表 # 根据 前序遍历 修改ans = []cur, pre = root, None while cur:if not cur.right:ans.append(cur.val) ##cur = cur.left# 有右孩子else:# 找 pre pre = cur.right while pre.left and pre.left != cur:pre = pre.left if not pre.left: ## 找到 mostleftpre.left = curans.append(cur.val) ## cur = cur.rightelse:pre.left = None cur = cur.leftreturn ans[::-1]
写法二
# 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 = right
class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:""" 后序遍历 [ 左子树 右子树 根 ] Morris O(N) O(1)"""## 需要 增加 一个 反转模块def addPath(node: TreeNode):count = 0while node:count += 1ans.append(node.val)node = node.righti, j = len(ans) - count, len(ans) - 1while i < j:ans[i], ans[j] = ans[j], ans[i]i += 1j -= 1### ans = []cur, pre = root, None while cur:if not cur.left:cur = cur.right # 有左孩子else:# 找 pre pre = cur.left while pre.right and pre.right != cur:pre = pre.right if not pre.right:pre.right = curcur = cur.left else:pre.right = None addPath(cur.left) ## cur = cur.right addPath(root) ## return ans C++
方法一： 递归 ⟮ O ( n ) ⟯ \lgroup O(n) \rgroup ⟮O(n)⟯
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:// 子模块void postorder(TreeNode* node, vector<int> &ans){if (node == nullptr){return;}postorder(node->left, ans);postorder(node->right, ans);ans.emplace_back(node->val);}// 主模块vector<int> postorderTraversal(TreeNode* root) {vector<int> ans;postorder(root, ans);return ans;}
};
方法二： 迭代 ⟮ O ( n ) ⟯ \lgroup O(n) \rgroup ⟮O(n)⟯
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> ans;stack<TreeNode*>stk;TreeNode* cur = root;TreeNode* pre = nullptr;while (cur != nullptr || !stk.empty()){while (cur != nullptr){stk.emplace(cur);cur = cur->left;}cur = stk.top();stk.pop();if (cur->right == nullptr || cur->right == pre){// 右子树 遍历完，处理根结点ans.emplace_back(cur->val);pre = cur;cur = nullptr;}else{// 右子树stk.emplace(cur);cur = cur->right;}}return ans;}
};
方法三： Morris ⟮ O ( n ) 、 O ( 1 ) ⟯ \lgroup O(n)、O(1) \rgroup ⟮O(n)、O(1)⟯
写法一
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> ans;TreeNode* cur = root;TreeNode* pre = nullptr;while (cur != nullptr){if (cur->right == nullptr){ans.emplace_back(cur->val);cur = cur->left;}else{// 找 pre pre = cur->right;while (pre->left != nullptr && pre->left != cur){pre = pre->left;}if (pre->left == nullptr){pre->left = cur;ans.emplace_back(cur->val);cur = cur->right;}else{pre->left = nullptr;cur = cur->left;}}}reverse(ans.begin(), ans.end()); // 该函数为 void ,不能直接返回return ans;}
};
写法二
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:// 子模块void addPath(TreeNode* node, vector<int> &ans){int count = 0;while (node != nullptr){count += 1;ans.emplace_back(node->val);node = node->right;}int i = ans.size() - count, j = ans.size() - 1;while (i < j){swap(ans[i], ans[j]);i += 1;j -= 1;}}// 主模块vector<int> postorderTraversal(TreeNode* root) {vector<int> ans;TreeNode* cur = root;TreeNode* pre = nullptr;while (cur != nullptr){if (cur->left == nullptr){cur = cur->right;}else{//找 pre pre = cur->left;while (pre->right != nullptr && pre->right != cur){pre = pre->right;}if (pre->right == nullptr){pre->right = cur;cur = cur->left;}else{pre->right = nullptr;addPath(cur->left, ans);cur = cur->right;}}}addPath(root, ans);return ans;}
};
这篇关于【LeetCode】145. 二叉树的后序遍历 [ 左子树 右子树 根结点]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
