Non-recursive preorder traverse Java solution


  • 17
    L
    public class Solution {
            public int sumNumbers(TreeNode root) {
                if(root==null){
                    return 0;
                }
                int sum = 0;
                TreeNode curr;
                Stack<TreeNode> ws = new Stack<TreeNode>();
                ws.push(root);
                
                while(!ws.empty()){
                    curr = ws.pop();
                    
                    if(curr.right!=null){
                        curr.right.val = curr.val*10+curr.right.val;
                        ws.push(curr.right);
                    }
                    
                    if(curr.left!=null){
                        curr.left.val = curr.val*10+curr.left.val;
                        ws.push(curr.left);
                    }
                    
                    if(curr.left==null && curr.right==null){ // leaf node
                        sum+=curr.val;
                    }
                }
                return sum;
            }
        }

  • -1
    H

    I think this is a level order traversal solution, though the normal method is using queue to store node and here you use stack. But still a good solution, iteratively. Thanks for sharing.


  • -1
    Y

    no,I think it is dfs, storing both children nodes aims at returning from one finished path.


  • 0
    X

    it`s actually preorder, not level order, you may print the path and see.


  • 0
    R

    i also think it is DFS,not preorder( its order:root ,root.right,root.right.right...),not level order


  • 0
    P

    Your code modified value of each node, which is not ideal.


  • 0
    D

    I think it is not preorder, it's level order using BFS.


  • 0
    D

    @demonxiaojian said in Non-recursive preorder traverse Java solution:

    I think it is not preorder, it's level order using BFS.

    and your code modified value of each node, which is not ideal, you may use a list to store it.


  • 0
    M
    This post is deleted!

  • 0
    M

    @lxclinton I like the way you solved using Preorder traversal iteratively. It's different from others, that said, changing a value of each node may not be ideal sometimes. Nevertheless, it looks different !!!


  • 0
    J

    its good to come up with a non-recursive solution. however currently you are changing the value of the treeNode which is not ideal


  • 0
    Z

    It is actually pre-order.
    Since it is using a stack, it puts three if statement: right node, left node, leaf node into the stack.

    But when we pop out of stack(LIFO) we reverse that order, we actually start from root, then left, then right, so it is definitely pre-order. Smart solution!


Log in to reply
 

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