Easy to understand Postorder Traversal solution


  • 0
    K
    public static TreeNode lowestCommonAncestorIterative(TreeNode root, TreeNode p, TreeNode q) {
    
            if (root == null || p == root || q== root) {
                return root;
            }
    
            Stack<TreeNode> stack = new Stack<>();
            TreeNode candidate = null;
            TreeNode prev = null;
            
            while(!stack.isEmpty() || root!=null){
    
                while(root!=null){
                    stack.push(root);
                    if(root == p || root == q){
                        if(candidate!=null && candidate!=root)
                            return candidate;
                        else
                            candidate = root;
                    }
                    root = root.left;
                }
    
                root = stack.peek();
                
                if(root.right!=null && prev!=root.right){
                    root = root.right;
                }
                else{
                    prev = root;
                    stack.pop();
                    if(root == candidate)
                        candidate = stack.peek();
                    root = null;
                }
    
            }
            return candidate;
        }
    

Log in to reply
 

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