11
LeetCode: 94. Binary Tree Inorder Traversal
source link: https://mozillazg.com/2020/11/leetcode-94-binary-tree-inorder-traversal.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题目¶
原题地址：https://leetcode.com/problems/binary-tree-inorder-traversal/
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3] Output: [1,3,2]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Example 4:
Input: root = [1,2] Output: [2,1]
Example 5:
Input: root = [1,null,2] Output: [1,2]
Constraints:
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Follow up:
- Recursive solution is trivial, could you do it iteratively?
解法¶
递归法实现中序遍历¶
这个方法的 Python 代码类似下面这样:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def inorderTraversal(self, root):
nodes = []
self._inorder(nodes, root)
return nodes
def _inorder(self, nodes, root):
if root is None:
return
self._inorder(nodes, root.left)
nodes.append(root.val)
self._inorder(nodes, root.right)
stack 法实现中序遍历¶
这个方法的 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):
nodes = []
stack = []
curr = root
while curr is not None or stack:
while curr is not None:
stack.append(curr)
curr = curr.left
curr = stack.pop()
nodes.append(curr.val)
curr = curr.right
return nodes
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK