Python每日一练(20230329)
目录
1. 二叉树的前序遍历 🌟🌟
2. 二叉树的中序遍历 🌟🌟
3. 二叉树的后序遍历 🌟🌟
🌟 每日一练刷题专栏 🌟
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
1. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,2,3]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[1,2]
示例 5：
输入：root = [1,null,2] 输出：[1,2]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
出处：
https://edu.csdn.net/practice/24062023
代码1：
from typing import Listclass TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def __init__(self):self.ans = []def preorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []self.ans.append(root.val)self.preorderTraversal(root.right)self.preorderTraversal(root.left)return self.ansdef listToTree(lst: List[int]) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return root# %%
s = Solution()
null = None
nums = [1,null,2,3]
root = listToTree(nums)print(s.preorderTraversal(root))
代码2： 迭代
from typing import Listclass TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []res, stack = [], []stack.append(root)while stack:node = stack.pop()res.append(node.val)if node.right:stack.append(node.right)if node.left:stack.append(node.left)return resdef listToTree(lst: List[int]) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return root# %%
s = Solution()
null = None
nums = [1,null,2,3]
root = listToTree(nums)print(s.preorderTraversal(root))
输出：
[1, 2, 3]
2. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[2,1]
示例 5：
输入：root = [1,null,2] 输出：[1,2]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
出处：
https://edu.csdn.net/practice/24062024
代码1： 递归
from typing import Listclass TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def __init__(self):self.ans = []def inorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []self.inorderTraversal(root.right)self.ans.append(root.val)self.inorderTraversal(root.left)return self.ansdef listToTree(lst: List[int]) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return root# %%
s = Solution()
null = None
nums = [1,null,2,3]
root = listToTree(nums)print(s.inorderTraversal(root))
代码2： 迭代
from typing import Listclass TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []res, stack = [], []while root or stack:while root:stack.append(root)root = root.leftnode = stack.pop()res.append(node.val)root = node.rightreturn resdef listToTree(lst: List[int]) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return root# %%
s = Solution()
null = None
nums = [1,null,2,3]
root = listToTree(nums)print(s.inorderTraversal(root))
代码3： 迭代(原题代码)
class TreeNode(object):def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass List2Tree(object):def __init__(self, nums: list):self.nums = numsself.queue = []if len(nums) == 1:self.root = TreeNode(self.nums.pop(0))else:a = self.nums.pop(0)b = self.nums.pop(0)c = self.nums.pop(0)self.root = TreeNode(a)if b is not None:self.root.left = TreeNode(b)else:self.root.left = bif c is not None:self.root.right = TreeNode(c)else:self.root.right = cself.queue.append(self.root.left)self.queue.append(self.root.right)def convert(self):while len(self.nums) > 0 and len(self.queue) > 0:node = self.queue.pop(0)if node is not None:num= self.nums.pop(0)if num is not None:node.left = TreeNode(num)else:node.left = numif len(self.nums) > 0:num = self.nums.pop(0)else:num = Noneif num is not None:node.right = TreeNode(num)else:node.right = numself.queue.append(node.left)self.queue.append(node.right)return self.rootclass Solution(object):def inorderTraversal(self, root):if root is None:return []root = List2Tree(root).convert()res = []stack = [root]while len(stack) > 0:curr = stack.pop()if not isinstance(curr, TreeNode):res.append(curr)continueif curr.right is not None:stack.append(curr.right)stack.append(curr.val)if curr.left is not None:stack.append(curr.left)return res# %%
s = Solution()
print(s.inorderTraversal(root = [1,None,2,3]))输出：
[1, 3, 2]
3. 二叉树的后序遍历
给你二叉树的根节点 root ，返回它节点值的 后序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[3,2,1]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[1,2]
示例 5：
输入：root = [1,null,2] 输出：[1,2]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
代码1： 递归
from typing import Listclass TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def __init__(self):self.ans = []def postorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []self.postorderTraversal(root.right)self.postorderTraversal(root.left)self.ans.append(root.val)return self.ansdef listToTree(lst: List[int]) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return root# %%
s = Solution()
null = None
nums = [1,null,2,3]
root = listToTree(nums)print(s.postorderTraversal(root))
代码2： 迭代
from typing import Listclass TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []res = []stack = []prev = Nonewhile stack or root:while root:stack.append(root)root = root.leftroot = stack.pop()if not root.right or root.right == prev:res.append(root.val)prev = rootroot = Noneelse:stack.append(root)root = root.rightreturn resdef listToTree(lst: List[int]) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return root# %%
s = Solution()
null = None
nums = [1,null,2,3]
root = listToTree(nums)print(s.postorderTraversal(root))
代码3： 遍历出反向结果后翻转列表
from typing import Listclass TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []res, stack = [], []stack.append(root)while stack:node = stack.pop()res.append(node.val)if node.left:stack.append(node.left)if node.right:stack.append(node.right)return res[::-1]def listToTree(lst: List[int]) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return root# %%
s = Solution()
null = None
nums = [1,null,2,3]
root = listToTree(nums)print(s.postorderTraversal(root))
输出：
[3, 2, 1]
其它写法：
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res, tmp, stack = [], [], []
while stack or root:
while root:
tmp.append(root.val)
stack.append(root)
root = root.right
if stack:
root = stack.pop().left
while tmp:
res.append(tmp.pop())
return res
前中后序递归比较：
from typing import Listclass TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []res = []res.append(root.val)res.extend(self.preorderTraversal(root.left))res.extend(self.preorderTraversal(root.right))return resdef inorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []res = []res.extend(self.inorderTraversal(root.left))res.append(root.val)res.extend(self.inorderTraversal(root.right))return resdef postorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []res = []res.extend(self.postorderTraversal(root.left))res.extend(self.postorderTraversal(root.right))res.append(root.val)return resdef listToTree(lst: List[int]) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return root# %%
s = Solution()
null = None
nums = [1,null,2,3]
root = listToTree(nums)
print(s.preorderTraversal(root))
print(s.inorderTraversal(root))
print(s.postorderTraversal(root))nums = [i for i in range(1,16)]
root = listToTree(nums)
print(s.preorderTraversal(root))
root = listToTree(nums)
print(s.inorderTraversal(root))
root = listToTree(nums)
print(s.postorderTraversal(root))
[1, 2, 3]
[1, 3, 2]
[3, 2, 1]
[1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15]
[8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15]
[8, 9, 4, 10, 11, 5, 2, 12, 13, 6, 14, 15, 7, 3, 1]
前中后序迭代比较：
from typing import Listclass TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []res, stack = [], []stack.append(root)while stack:node = stack.pop()res.append(node.val)if node.right:stack.append(node.right)if node.left:stack.append(node.left)return resdef inorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []res, stack = [], []while root or stack:while root:stack.append(root)root = root.leftnode = stack.pop()res.append(node.val)root = node.rightreturn resdef postorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []res, stack = [], []while root or stack:while root:res.append(root.val)stack.append(root)root = root.rightif stack:root = stack.pop().leftreturn res[::-1]def listToTree(lst: List[int]) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return root# %%
s = Solution()
null = None
nums = [1,null,2,3]
root = listToTree(nums)
print(s.preorderTraversal(root))
print(s.inorderTraversal(root))
print(s.postorderTraversal(root))nums = [i for i in range(1,16)]
root = listToTree(nums)
print(s.preorderTraversal(root))
print(s.inorderTraversal(root))
print(s.postorderTraversal(root))
[1, 2, 3]
[1, 3, 2]
[3, 2, 1]
[1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15]
[8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15]
[8, 9, 4, 10, 11, 5, 2, 12, 13, 6, 14, 15, 7, 3, 1]
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
 |
Golang每日一练 专栏 |
 |
Python每日一练 专栏 |
 |
C/C++每日一练 专栏 |
 |
Java每日一练 专栏 |
