Iterative solution based on pre-order traversal


  • 0
    B

    There's already a good summary about iterate through binary tree in non-recursion way: https://discuss.leetcode.com/topic/30632/preorder-inorder-and-postorder-iteratively-summarization

    This non-recursion solution to "Sum Root to Leaf Numbers" is just a minor change based on the pre-order traversal.

        private int sum = 0
        public int sumNumbers(TreeNode root) {
            traverse(root);
            return sum;
        }
        // pre-order traversal
        private void traverse(TreeNode root) {
            TreeNode p = root;
            LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    
            // maintain a parent node, it's value will be used to update current node's value
            TreeNode parent = null;
    
            while ( p != null || !stack.isEmpty() ) {
                if (p != null) {
    
                    if (parent != null)
                        p.val = parent.val * 10 + p.val;
    
                    if (p.left == null && p.right == null)
                        sum += p.val;
    
                    parent = p;
                    stack.push(p);
                    p = p.left;
                } else {
                    TreeNode node = stack.pop();
                    p = node.right;
    
                    // attention: here 'parent' is the node just get poped
                    if (p != null)
                        parent = node;
                }
            }
        }
    

Log in to reply
 

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