【Leetcode 94】二叉树的中序遍历

题目描述

解法一：颜色标记法

解题代码

class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
WHITE, GRAY = 0, 1
res = []
stack = [(WHITE, root)]
while stack:
color, node = stack.pop()
if node is None: continue
if color == WHITE:
stack.append((WHITE, node.right))
stack.append((GRAY, node))
stack.append((WHITE, node.left))
else:
res.append(node.val)
return res

解法二：使用递归

python版本

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self,root: TreeNode) -> List[int]:
res=[]
self.inorder(root,res)
return res

def inorder(self,root:TreeNode,res:List):
if (root==None): return

self.inorder(root.left,res)
res.append(root.val)
self.inorder(root.right,res)

解法三：使用栈

java版本

本题用Deque构造队列，也可以用stack这种数据结构

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stk = new LinkedList<TreeNode>();
while (root != null || !stk.isEmpty()) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
res.add(root.val);
root = root.right;
}
return res;
}
}

这里使用到了Java的Deque双端队列，注意push和pop方法都是针对表头元素做操作

更多deque队列的用法

参考链接
​​​ https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/​​ https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/