My Stack-based iterative solution C#


  • 0
    S
    public class TreeNodeVisitedData { 
        public TreeNode actual;
        public bool visitedLeft; 
        public bool visitedRight;
        
        public TreeNodeVisitedData(TreeNode actualNode) {
            actual = actualNode;
        }
    }
    
    public class Solution {
        public bool IsSameTree(TreeNode p, TreeNode q) {
            Console.WriteLine("Start");
            if (p != null && q != null) {
                Stack<TreeNodeVisitedData> s1 = new Stack<TreeNodeVisitedData>();
                Stack<TreeNodeVisitedData> s2 = new Stack<TreeNodeVisitedData>();
                
                TreeNode current1 = p;
                TreeNode current2 = q;
                
                while (true) {
                    Console.WriteLine("Starting while true loop2" + current1 + " cur2 " + current2);
                    if (current1 == null && current2 == null) {
                        Console.WriteLine("do nothing");
                    } else {
                        if (current1 != null && current2 != null) {
                            Console.WriteLine("current 1 is not null and current 2 is not null: " + current1.val  + " " + current2.val);
                            s1.Push(new TreeNodeVisitedData(current1));
                            s2.Push(new TreeNodeVisitedData(current2));
                        } else {                    
                            Console.WriteLine("one of current1 or current2 is null");
                            // If one is null and the other is not there is a problem.
                            return false;
                        }
                    }
                    
                    
                    if (s1.Count == 0 && s2.Count == 0) {
                        Console.WriteLine("Stacks are empty");
                    
                        // we are done. 
                        return true;                    
                    } else if (s1.Count != 0 && s2.Count != 0) {
                        
                        TreeNodeVisitedData top1 = s1.Peek();
                        TreeNodeVisitedData top2 = s2.Peek();
                        
                        Console.WriteLine("Tops: " + top1.actual.val + " " + top2.actual.val);
                        // first time do the actual check.
                        if (top1.actual.val != top2.actual.val) {
                            return false;
                        }                    
                        
                        if (!top1.visitedLeft) {
                            
                            current1 = top1.actual.left;
                            current2 = top2.actual.left;                       
                            
                            
                            if (current1 == null && current2 == null) {
                                Console.WriteLine("Visiting Lefts: Both are null");
                            } else {
                                Console.WriteLine("Visiting Lefts: " + current1 + " " + current2);    
                            }
                        
                            
                            top1.visitedLeft = true;
                            top2.visitedLeft = true;                        
                            
                        } else if (!top1.visitedRight) {
                            current1 = top1.actual.right;
                            current2 = top2.actual.right;
                            
                            top1.visitedRight = true;
                            top2.visitedRight = true;
                            
                            Console.WriteLine("Visiting right: " + current1 + " " + current2);
                            
                        
                            // Both left and right are done. So, pop. 
                            s1.Pop();
                            s2.Pop();
                        }
                    } else {
                        // if one of them is empty, there is a problem. 
                        return false;
                    }                
                }                
            } else if (p == null && q == null) {
                Console.WriteLine("Both p and q are null");
                return true;
            } else {
                return false;
            }
        } 
    }```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.