LEETCODEEasy
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]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
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?
풀이 TypeScript
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function inorderTraversal(root: TreeNode | null): number[] {
const result: number[] = [];
const visit = (node: TreeNode | null): void => {
if (node === null) return;
visit(node.left);
result.push(node.val);
visit(node.right);
};
visit(root);
return result;
}
function inorderTraversalIterative(root: TreeNode | null): number[] {
const result: number[] = [];
const stack: TreeNode[] = [];
let curr = root;
while (curr || stack.length) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop()!;
result.push(curr.val);
curr = curr.right;
}
return result;
}
복사됨