Java non-recursive post-order traversal solution


  • 1
    C

    So, the idea is to use the classic post-order tree traversal, and keep track of the sum of current root-to-leaf path. Whenever the leaf is hit, add that sum to the whole sum.

    public static int sumNumbers(TreeNode root) {
        int sum = 0, num = 0;
        TreeNode lastVisited = null;
        Stack<TreeNode> s = new Stack<>();
        while (root != null || !s.isEmpty()) {
            if (root != null) {
                s.push(root);
                num = num * 10 + root.val;
                root = root.left;
            } else {
                TreeNode peek = s.peek();
                if (peek.right != lastVisited && peek.right != null) {
                    root = peek.right;
                } else {
                    if (peek.left == null && peek.right == null) {
                        sum += num;
                    }
                    s.pop();
                    num /= 10;
                    lastVisited = peek;
                }
            }
        }
        return sum;
    
    }

Log in to reply
 

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