二叉树的中序遍历(难度:中等)
中序遍历:左-中-右
方法一:递归
定义一个辅助函数来实现递归。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public List < Integer > inorderTraversal(TreeNode root) { List < Integer > res = new ArrayList < > (); helper(root, res); return res; }
public void helper(TreeNode root, List < Integer > res) { if (root != null) { if (root.left != null) { helper(root.left, res); } res.add(root.val); if (root.right != null) { helper(root.right, res); } } } }
|
复杂度
时间复杂度:O(n)。递归函数 T(n) = 2 T(n/2)+1。
空间复杂度:最坏情况下需要空间O(n),平均情况为O(logn)。
方法二:迭代
颜色标记法:
作者:hzhu212
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/
来源:力扣(LeetCode)
其核心思想如下:
- 使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色。
- 如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈。
- 如果遇到的节点为灰色,则将节点的值输出。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
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 == 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
|
如要实现前序、后序遍历,只需要调整左右子节点的入栈顺序即可。
另一种写法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: stack = [] res = [] while True: while root: stack.append(root) root = root.left if not stack: return res root = stack.pop() res.append(root.val) root = root.right
|
复杂度
时间复杂度:O(n)。
空间复杂度:O(n)。
算法 |
执行用时 |
内存消耗 |
语言 |
方法二:迭代(另一种写法) |
28 ms |
13 MB |
Python3 |
方法二:迭代(颜色标价法) |
36 ms |
12.7 MB |
Python3 |
方法一:递归 |
0 ms |
34.6 MB |
Java |