March 21, 2022
Here is the link.
C# | Post order | Study discuss post | Solve TLE problem
March 21, 2022
Introduction
It is humble experience to learn how to write a post order traversal and learn how to record from node to root node path, and also apply conditional search by checking return value of recursive function. Recursive function design is challenge and then I started to look for working solution first.
Test case | Example
Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
The path to found destValue 6 is "LR" instead of "RL", bottom up, post order, and it is the path from source node to root node.
I chose to use preorder traversal, build prefix string first but it ran into TLE error, Preorder practice | TLE error. Compared to preorder traversal, postorder traversal the path is not built for those failed paths so it is more efficient, much less string concatenation manipulation operations, only for valid path. No worry about TLE error. This lesson is learned so surprisingly and efficiently.
Post order traversal | Find path | C# StringBuilder
I just learned how to write a working solution using discuss post, and then learn a few others as well.
The following C# code passes online judge.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _2096_step_by_step
{
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 node5 = new TreeNode(5);
node5.left = new TreeNode(1);
node5.right = new TreeNode(2);
node5.left.left = new TreeNode(3);
node5.right.left = new TreeNode(6);
node5.right.right = new TreeNode(4);
var test = new Program();
var start = test.GetDirections(node5, 3, 6);
//var end = test.GetDirections(node5,6, 3);
}
/// <summary>
/// March 21, 2022
/// Find startValue using 'L','R','U'
/// Find endValue using 'L','R','U'
/// study code:
/// https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/discuss/1617344/C-Solution
/// </summary>
/// <param name="root"></param>
/// <param name="startValue"></param>
/// <param name="destValue"></param>
/// <returns></returns>
public string GetDirections(TreeNode root, int startValue, int destValue)
{
var startPath = new StringBuilder();
var destPath = new StringBuilder();
runPostorderSearch(root, startValue, startPath);
runPostorderSearch(root, destValue, destPath);
startPath = new StringBuilder(new string(startPath.ToString().Reverse().ToArray()));
destPath = new StringBuilder(new string(destPath.ToString().Reverse().ToArray()));
while (startPath.Length > 0 && destPath.Length > 0 && startPath[0] == destPath[0])
{
startPath.Remove(0, 1);
destPath.Remove(0, 1);
}
for (int i = 0; i < startPath.Length; ++i)
{
if (startPath[i] == 'L' || startPath[i] == 'R')
{
startPath[i] = 'U';
}
}
return startPath.ToString() + destPath.ToString();
}
/// <summary>
/// Lessons learned:
/// preorder traversal, search left subtree, if not found then search right subtree.
/// It is conditional search. Do not search right subtree unless search of left subtree fails
/// Use bool value for preorder traversal
/// reverse order - postorder - not preorder
/// </summary>
/// <param name="root"></param>
/// <param name="value"></param>
/// <param name="path"></param>
/// <returns></returns>
public bool runPostorderSearch(TreeNode root, int value, StringBuilder path)
{
if (root.val == value)
{
return true;
}
else if (root.left != null && runPostorderSearch(root.left, value, path))
{
path.Append("L"); // Do not assign new StringBuilder, change pointer address
return true;
}
else if (root.right != null && runPostorderSearch(root.right, value, path))
{
path.Append("R");
return true;
}
else
{
return false;
}
}
}
}
