0094-binary-tree-inorder-traversal.cs

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * public int val;
 * public TreeNode left;
 * public TreeNode right;
 * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
publicclassSolution{
publicIList<int>InorderTraversal(TreeNoderoot){
// return InorderTraversalRecursive(root).ToList();
returnInorderTraversalIterative(root).ToList();
}

// Time: O(n)
// Space: O(n)
privateIEnumerable<int>InorderTraversalRecursive(TreeNodenode){
if(node==null){
returnEnumerable.Empty<int>();
}

returnInorderTraversalRecursive(node.left)
.Append(node.val)
.Concat(InorderTraversalRecursive(node.right));
}

// Time: O(n)
// Space: O(n)
privateIEnumerable<int>InorderTraversalIterative(TreeNodenode){
List<int>result=new();
Stack<TreeNode>stack=new();
while(node!=null||stack.Any()){
while(node!=null){
stack.Push(node);
node=node.left;
}
node=stack.Pop();
result.Add(node.val);
node=node.right;
}
returnresult;
}
}