Posted on | Edited on | Views:

https://leetcode.com/problems/sum-root-to-leaf-numbers/

1
2
3
4
5
6
7
8
9
10
11
//   Definition for a binary tree node.
public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val; this.left = left; this.right = right;
      }
  }

My solution: LinkedList + Backtracking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    int res=0;
    public int sumNumbers(TreeNode root) {
        if(root==null) return 0;
        // using a list to store all the numbers from root to leaves,
        // not necessarily need to use it.
        recursion(root,new LinkedList<>());
        return res;
    }
    public void recursion(TreeNode node,LinkedList<Integer> ls){
        if(node.left==null&&node.right==null){
            int cnt=ls.size();
            int i=0;
            while(cnt>0)res+=ls.get(i++)*Math.pow(10,cnt--);
            res+=node.val;
            return;
        }
        ls.offer(node.val);
        if(node.left!=null) recursion(node.left,ls);
        if(node.right!=null) recursion(node.right,ls);
        ls.removeLast();
    }
}

Leetcode Solution: Recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution_1 {
    int res=0;
    public int sumNumbers(TreeNode root) {
        if(root==null) return 0;
        recur_sum(root,0);
        return res;
    }
    public void recur_sum(TreeNode node,int sum){
        if(node!=null){
            sum=sum*10+node.val;
            if(node.left==null&&node.right==null){
                res+=sum;
            }
            recur_sum(node.left,sum);
            recur_sum(node.right,sum);
        }
    }
}
// more concise version
class Solution_2 {
    public int sumNumbers(TreeNode root) {
	return sum(root, 0);
    }

public int sum(TreeNode n, int s){
	if (n == null) return 0;
	if (n.right == null && n.left == null) return s*10 + n.val;
	return sum(n.left, s*10 + n.val) + sum(n.right, s*10 + n.val);
    }
}

Morris Preorder Traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) {this.val = val;}
  TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

class lt129 {
  public static int sumNumbers(TreeNode root) {
    int rootToLeaf = 0, currNumber = 0;
    int steps;
    TreeNode predecessor;

    while (root != null) {
      // If there is a left child,
      // then compute the predecessor.
      // If there is no link predecessor.right = root --> set it.
      // If there is a link predecessor.right = root --> break it.
      if (root.left != null) {
        // Predecessor node is one step to the left
        // and then to the right till you can.
        predecessor = root.left;
        steps = 1;
        while (predecessor.right != null && predecessor.right != root) {
          predecessor = predecessor.right;
          ++steps;
        }

        // Set link predecessor.right = root
        // and go to explore the left subtree
        if (predecessor.right == null) {
          currNumber = currNumber * 10 + root.val;
          predecessor.right = root;
          root = root.left;
        } else { // Break the link predecessor.right = root Once the link is broken, it's time to
                 // change subtree and go to the right
          // If you're on the leaf, update the sum
          if (predecessor.left == null) {
            rootToLeaf += currNumber;
          }
          // This part of tree is explored, backtrack
          for (int i = 0; i < steps; ++i) {
            currNumber /= 10;
          }
          predecessor.right = null;
          root = root.right;
        }
      } else {// If there is no left child then just go right.
        currNumber = currNumber * 10 + root.val;
        // if you're on the leaf, update the sum
        if (root.right == null) {
          rootToLeaf += currNumber;
        }
        root = root.right;
      }
    }
    return rootToLeaf;
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(4);
    root.left = new TreeNode(9);
    root.right = new TreeNode(0);
    root.left.left = new TreeNode(5);
    root.left.right = new TreeNode(1);

    sumNumbers(root);
  }
}

0%