longest-zigzag-path.dart (1526B)
1 // For this one I am not adding a constructor thus it can not run without being setup. 2 // This solution causes a stack overflow error on leet-code because in leet-code 3 // the tree size can be 50000 elements in size which is frankly unreasonable so this 4 // stops working at a certain point depending on the way the data is structured. 5 // Nonetheless this will work in 99% of real world use cases, and it will return the longest 6 // zig zagging pattern through the tree that does not contain any null values. 7 // The time complexity of the algorithm is O(N) because it visits all nodes only once. 8 // In theory to make this algorithm support larger data sets you could use a queue, but 9 // this works and I don't think I would learn anything by changing this. 10 11 12 /** 13 * Definition for a binary tree node. 14 * class TreeNode { 15 * int val; 16 * TreeNode? left; 17 * TreeNode? right; 18 * TreeNode([this.val = 0, this.left, this.right]); 19 * } 20 */ 21 class Solution { 22 TreeNode? thousand; 23 int max = 0; 24 25 26 int longestZigZag(TreeNode? root) { 27 28 solve(root?.left, 1 , false); 29 solve(root?.right, 1 , true); 30 return max; 31 } 32 33 34 void solve(TreeNode? current, int depth , bool right){ 35 36 if(current?.val == null){ 37 return; 38 } 39 if(depth > max){ 40 max = depth; 41 } 42 if(right){ 43 solve(current?.left, depth + 1, false); 44 solve(current?.right, 1, true); 45 } 46 else{ 47 solve(current?.right, depth + 1, true); 48 solve(current?.left, 1, false); 49 } 50 } 51 }