August 23, 2022
Here is the link.
C# | Quick learner | using recursive function or stack
August 23, 2022
I like to write a working solution using recursive function, and review my last practice back in 2018.
Solution 1:
I choose to use C# List and also write a function to pass List as a function argument, so all nodes in the tree will be visited once and be added to List in inorder traversal order.
Space complexity: Using O(N) space, List
Time complexity: O(N), N is the total number of nodes in the tree
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _94_inorder_traversal
{
class Program
{
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;
}
}
static void Main(string[] args)
{
var root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);
var list = InorderTraversal(root);
Debug.Assert(string.Join(",", list).CompareTo("1,3,2") == 0);
}
/// <summary>
/// emtpy tree, with one root node, with more nodes
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public static IList<int> InorderTraversal(TreeNode root)
{
var list = new List<int>();
runInorderTraversal(root, list);
return list;
}
private static void runInorderTraversal(TreeNode root, IList<int> list)
{
if (root == null)
{
return;
}
runInorderTraversal(root.left, list);
list.Add(root.val);
runInorderTraversal(root.right, list);
}
}
}
Solution 2 | Using stack | iterative solution
I think that the design should be simple. Go over a few test cases, and then complete the design.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _94_inorder_traversal_iterative
{
class Program
{
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;
}
}
static void Main(string[] args)
{
var root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);
var list = InorderTraversal(root);
Debug.Assert(string.Join(",", list).CompareTo("1,3,2") == 0);
}
/// <summary>
/// study code
///
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public static IList<int> InorderTraversal(TreeNode root)
{
var list = new List<int>();
if (root == null)
{
return list;
}
// stack - inorder - left, root, right
var stack = new Stack<TreeNode>();
var current = root;
// stack
// design - visit left child and right child at least once
// put left child first, before root node itself.
// stack.Push - only once - in coding writing
// stack.Pop - only once - in coding writing
//
while (stack.Count > 0 || current != null)
{
// Go over an example
// Binary tree - Test case 1:
// root = new TreeNode(1);
// root.left = new TreeNode(2);
// root.left.left = new TreeNode(3);
// nodes should be pushed into stack: push 1, push 2, push 3
// Work on test case 1, and then add a right node into tree, work on test case 2 to cover all test cases.
while (current != null)
{
stack.Push(current);
current = current.left;
}
// Pop()
current = stack.Pop();
list.Add(current.val);
// Go to right
current = current.right;
}
return list;
}
}
}
Solution 3:
Oct. 4, 2018
It is a medium level tree algorithm. I submitted the solution more than four months ago. I like to review the code before I start to work on other 20 medium level tree algorithms. It is also a good idea to share here.
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public IList<int> InorderTraversal(TreeNode root) // emtpy tree, with one root node, with more nodes
{
if (root == null)
{
return new List<int>();
}
var left = InorderTraversal(root.left);
left.Add(root.val);
var right = InorderTraversal(root.right);
// add right to left list <- code review on August 23, 2022, it is not a good practice.
if (right.Count > 0)
{
foreach (var item in right)
{
left.Add(item);
}
}
return left;
}
}
I think that it is better to avoid copying the list from right variable to left. It takes extra time and no need to do that.
