1. 問題的描述
給你二叉樹的根節點 root ，傳回它節點值的 前序 周遊。
前序周遊首先通路根結點然後周遊左子樹，最後周遊右子樹。在周遊左、右子樹時，仍然先通路根結點，然後周遊左子樹，最後周遊右子樹。若二叉樹為空則結束傳回，否則：
（1）通路根結點。
（2）前序周遊左子樹。
（3）前序周遊右子樹 。需要注意的是：周遊左右子樹時仍然采用前序周遊方法。
如圖所示二叉樹，前序周遊結果：ABDECF
給你二叉樹的根節點 root ，傳回它節點值的前序周遊。
示例 1:
輸入: root = [1,None,2,3]
輸出: [1,2,3]
示例 2:
輸入: root = []
輸出: []
示例 3:
輸入: root = [1]
輸出: [1]
示例 4:
輸入: root = [1,2]
輸出: [1,2]
示例 5:
輸入: root = [1,None,2]
輸出: [1,2]
初始代碼
from typing import List
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def list_to_binarytree(nums):
if nums==[]:return
b=root=TreeNode(nums[0])
a=[]
i=1
while i < len(nums):
if nums[i]:
root.left=TreeNode(nums[i])
a.append(root.left)
if i+1<len(nums):
if nums[i+1]:
root.right=TreeNode(nums[i+1])
a.append(root.right)
i+=2
root=a.pop(0)
return b
root = list_to_binarytree([1,None,2,3,None,4,5,6,7,8])
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
#在此填寫代碼
print(Solution().preorderTraversal(list_to_binarytree([1,None,2,3])))
print(Solution().preorderTraversal(list_to_binarytree([])))
print(Solution().preorderTraversal(list_to_binarytree([1])))
print(Solution().preorderTraversal(list_to_binarytree([1,2])))
print(Solution().preorderTraversal(list_to_binarytree([1,None,2]))) 2. 解題思路
- 按照通路根節點——左子樹——右子樹的方式周遊這棵樹，而在通路左子樹或者右子樹的時候，我們按照同樣的方式周遊，直到周遊完整棵樹。
- 是以整個周遊過程天然具有遞歸的性質，我們可以直接用遞歸函數來模拟這一過程。
- 按照定義，我們隻要首先将 root 節點的值加入答案，然後調用遞歸來周遊 root 節點的左子樹，最後調用遞歸來周遊 root 節點的右子樹即可，遞歸終止的條件為碰到空節點。
3. 解題方法
from typing import List
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def list_to_binarytree(nums):
if nums==[]:return
b=root=TreeNode(nums[0])
a=[]
i=1
while i < len(nums):
if nums[i]:
root.left=TreeNode(nums[i])
a.append(root.left)
if i+1<len(nums):
if nums[i+1]:
root.right=TreeNode(nums[i+1])
a.append(root.right)
i+=2
root=a.pop(0)
return b
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
def a(x,root):
if root:
x.append(root.val)
a(x,root.left)
a(x,root.right)
return x
x=[]
return a(x,root)
print(Solution().preorderTraversal(list_to_binarytree([1,None,2,3])))
print(Solution().preorderTraversal(list_to_binarytree([])))
print(Solution().preorderTraversal(list_to_binarytree([1])))
print(Solution().preorderTraversal(list_to_binarytree([1,2])))
print(Solution().preorderTraversal(list_to_binarytree([1,None,2]))) 第1-26，36-40行： 題目中已經給出的資訊，運作代碼時要根據這些代碼進行編輯（具體為建立二叉樹以及清單、二叉樹轉換）
第27行： 定義函數a用于遞歸，内部變量root二叉樹以及x清單來存放二叉樹的節點
第28行： 當二叉樹節點存在時執行if内部操作
第29行： x清單中存放root二叉樹節點的值
第30行： 遞歸操作，開始周遊二叉樹的左子樹，再對此左子樹進行前序周遊操作
第31行： 遞歸操作，當左子樹周遊完成時，開始周遊二叉樹的右子樹，再對此右子樹進行前序周遊操作
第32行： 當根節點root的右子樹周遊完成，結束周遊并傳回清單x
第33行： 定義x為空清單
第34行： 傳回二叉樹的前序周遊結果
代碼運作結果為：
4. 結構講解
這裡用到了基礎結構：二叉樹，簡單講解下這個二叉樹：
連結清單
二叉樹（Binary tree）是樹形結構的一個重要類型。許多實際問題抽象出來的資料結構往往是二叉樹形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的存儲結構及其算法都較為簡單，是以二叉樹顯得特别重要。
二叉樹特點是每個結點最多隻能有兩棵子樹，且有左右之分。
結點：包含一個資料元素及若幹指向子樹分支的資訊
結點的度：一個結點擁有子樹的數目稱為結點的度
葉子結點：也稱為終端結點，沒有子樹的結點或者度為零的結點
分支結點：也稱為非終端結點，度不為零的結點稱為非終端結點
樹的度：樹中所有結點的度的最大值
結點的層次：從根結點開始，假設根結點為第1層，根結點的子節點為第2層，依此類推，如果某一個結點位于第L層，則其子節點位于第L+1層
樹的深度：也稱為樹的高度，樹中所有結點的層次最大值稱為樹的深度