Java iterative solution based on non-recursive inorder traverse


  • 0
    S

    Basic idea is pretty simple, use a flag to record from which direction(left or right link from its parent ) it haven been visited during the inorder-traverse. When current node(indicated byptr in my solution) moves to its left child, we should change the flag to true. And do the similar operation respectively when current node moves to its right child.
    Here is my solution:

     public static int sumOfLeftLeaves(TreeNode root) {
            if (root == null) return 0;
            if (root.left == null  && root.right == null) return 0;
            Stack<TreeNode> s = new Stack<>();
            TreeNode  ptr = root;
            int sum = 0;
            boolean isLeft = true;
            while (ptr != null || !s.isEmpty()) {
                while (ptr != null) {
                    s.push(ptr);
                    if (ptr.left == null && ptr.right == null && isLeft)   // identify left leaf node
                        sum += ptr.val;
                    ptr = ptr.left;
                    isLeft = true;  // change the flag to indicate current link comes from left.
                }
                ptr = s.pop();
                ptr = ptr.right;
                isLeft = false; // change the flag to record current link is from right;
            }
            return sum;
        }

Log in to reply
 

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