?LeetCode刷題實戰(zhàn)94：二叉樹的中序遍歷
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?二叉樹的中序遍歷，我們先來看題面：
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
Given the root of a binary tree, return the inorder traversal of its nodes' values.
題意
解題
# 先序
def?dfs(u):
????visited.append(u)
????dfs(u.left)
????dfs(u.right)
????
# 中序
def?dfs(u):
????dfs(u.left)
????visited.append(u)
????dfs(u.right)
????
????
# 后序
def?dfs(u):
????dfs(u.left)
????dfs(u.right)
????visited.append(u)
class Solution:
????def inorderTraversal(self, root:?TreeNode) -> List[int]:
????????ret?= []
????????stack = []
????????stack.append(root)
????????while?len(stack) > 0:
????????????# 獲取棧頂頂點
????????????cur = stack[-1]
????????????if?cur is?None:
????????????????stack.pop()
????????????????continue
????????????????
????????????# 如果左孩子存在，那么優(yōu)先遍歷左孩子
????????????if?cur.left?is?not None:
????????????????stack.append(cur.left)
????????????????# 把左指針置為空，防止死循環(huán)
????????????????# 這里也可以用set來維護
????????????????cur.left?= None
????????????????continue
????????????????
????????????# 左邊遍歷結(jié)束之后加入序列
????????????ret.append(cur.val)
????????????stack.pop()
????????????if?cur.right?is?not None:
????????????????stack.append(cur.right)? ? ? ??
????????return?ret
上期推文：