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]
Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
Solution
Approach #0: Recursive
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcinorderTraversal(root *TreeNode) (ans []int) {var dfs func(*TreeNode) dfs =func(node *TreeNode) {if node ==nil {return } dfs(node.Left) ans =append(ans, node.Val) dfs(node.Right) } dfs(root)return}
Approach #1: Iterative
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcinorderTraversal(root *TreeNode) (ans []int) { st := []*TreeNode{}for root !=nil||len(st) >0 {for root !=nil { st =append(st, root) root = root.Left } root = st[len(st)-1] st = st[:len(st)-1] ans =append(ans, root.Val) root = root.Right }return}