Post-order traversal iterative solution in C#


  • 0
    P
    /**
     * 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 class TreeNodeModified
            {
                public TreeNode node;
                public bool isVisited;
    
                public TreeNodeModified(TreeNode treeNode, bool isVisited = false)
                {
                    this.node = treeNode;
                    this.isVisited = isVisited;
                }
            }
    
            public IList<int> PostorderTraversal(TreeNode root)
            {
                IList<int> output = new List<int>();
                Stack<TreeNodeModified> stackNodes = new Stack<TreeNodeModified>();
    
                if (root == null)
                {
                    return output;
                }
    
                stackNodes.Push(new TreeNodeModified(root, true));
    
                if (root.right != null)
                {
                    stackNodes.Push(new TreeNodeModified(root.right));
                }
    
                if (root.left != null)
                {
                    stackNodes.Push(new TreeNodeModified(root.left));
                }
    
                while (stackNodes.Count != 0)
                {
                    TreeNodeModified rootModified = stackNodes.Pop();
    
                    if (rootModified.isVisited)
                    {
                        output.Add(rootModified.node.val);
                        continue;
                    }
    
                    stackNodes.Push(new TreeNodeModified(rootModified.node, true));
    
                    if (rootModified.node.right != null)
                    {
                        stackNodes.Push(new TreeNodeModified(rootModified.node.right));
                    }
    
                    if (rootModified.node.left != null)
                    {
                        stackNodes.Push(new TreeNodeModified(rootModified.node.left));
                    }
                }
    
                return output;
            }
    
    }
    

Log in to reply
 

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