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 List class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class 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.ans def listToTree(lst: List[int]) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root # %% s = Solution() null = None nums = [1,null,2,3] root = listToTree(nums) print(s.preorderTraversal(root))
代码2： 迭代
from typing import List class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class 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 res def listToTree(lst: List[int]) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return 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 List class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class 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.ans def listToTree(lst: List[int]) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root # %% s = Solution() null = None nums = [1,null,2,3] root = listToTree(nums) print(s.inorderTraversal(root))
代码2： 迭代
from typing import List class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class 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.left node = stack.pop() res.append(node.val) root = node.right return res def listToTree(lst: List[int]) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return 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 = x self.left = None self.right = None class List2Tree(object): def __init__(self, nums: list): self.nums = nums self.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 = b if c is not None: self.root.right = TreeNode(c) else: self.root.right = c self.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 = num if len(self.nums) > 0: num = self.nums.pop(0) else: num = None if num is not None: node.right = TreeNode(num) else: node.right = num self.queue.append(node.left) self.queue.append(node.right) return self.root class 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) continue if 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 List class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class 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.ans def listToTree(lst: List[int]) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root # %% s = Solution() null = None nums = [1,null,2,3] root = listToTree(nums) print(s.postorderTraversal(root))
代码2： 迭代
from typing import List class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: if not root: return [] res = [] stack = [] prev = None while stack or root: while root: stack.append(root) root = root.left root = stack.pop() if not root.right or root.right == prev: res.append(root.val) prev = root root = None else: stack.append(root) root = root.right return res def listToTree(lst: List[int]) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root # %% s = Solution() null = None nums = [1,null,2,3] root = listToTree(nums) print(s.postorderTraversal(root))
代码3： 遍历出反向结果后翻转列表
from typing import List class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class 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 None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return 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 List class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class 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 res def 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 res def 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 res def listToTree(lst: List[int]) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return 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 List class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class 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 res def inorderTraversal(self, root: TreeNode) -> List[int]: if not root: return [] res, stack = [], [] while root or stack: while root: stack.append(root) root = root.left node = stack.pop() res.append(node.val) root = node.right return res def 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.right if stack: root = stack.pop().left return res[::-1] def listToTree(lst: List[int]) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return 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]
