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 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] 

---

???? 每日一练刷题专栏 ????

✨ 持续，努力奋斗做强刷题搬运工！

???? 点赞，你的认可是我坚持的动力！ 

???? 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏