LeetCode-in-Dart
94. Binary Tree Inorder Traversal
Easy
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?
Solution
/**
* Definition for a binary tree node.
* class TreeNode {
* int val;
* TreeNode? left;
* TreeNode? right;
* TreeNode([this.val = 0, this.left, this.right]);
* }
*/
class Stack<T> {
final List<T> _items = [];
void push(T item) {
_items.add(item);
}
T pop() {
return _items.removeLast();
}
T peek() {
return _items.last;
}
bool get isEmpty {
return _items.isEmpty;
}
int get size {
return _items.length;
}
}
class Solution {
List<int> inorderTraversal(TreeNode? root) {
final result = List<int>.empty(growable: true);
final stack = Stack<TreeNode>();
while (root != null || !stack.isEmpty) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
result.add(root.val);
root = root.right;
}
return result;
}
}