Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- /**
- Recursive DFS Solution.
- Time Complexity = O(n). All nodes will be visited once.
- Space Complexity = O(n). Recursion stack can grow up to n size if the tree is skewed.
- */
- class Solution {
- public int sumNumbers(TreeNode root) {
- if (root == null) {
- return 0;
- }
- return sumNumbersHelper(root, 0);
- }
- public int sumNumbersHelper(TreeNode node, int currVal) {
- if (node == null) {
- return 0;
- }
- currVal = currVal * 10 + node.val;
- if (node.left == null && node.right == null) {
- return currVal;
- }
- return sumNumbersHelper(node.left, currVal) + sumNumbersHelper(node.right, currVal);
- }
- }
- /**
- Recursive Post Order Traversal
- Time Complexity: O(n) -> Each node is visited twice.
- Space Complexity: O(n) -> Stack can grow upto all nodes if the tree is skewed.
- */
- class Solution {
- public int sumNumbers(TreeNode root) {
- if (root == null) {
- return 0;
- }
- Stack<TreeNode> stack = new Stack<>();
- int result = 0;
- int num = 0;
- TreeNode cur = root;
- TreeNode pre = null;
- while (cur != null || !stack.isEmpty()) {
- while (cur != null) {
- stack.push(cur);
- num = num * 10 + cur.val;
- cur = cur.left;
- }
- cur = stack.peek();
- if (cur.right != null && pre != cur.right) {
- cur = cur.right;
- continue;
- }
- if (cur.left == null & cur.right == null) {
- result += num;
- }
- pre = stack.pop();
- num /= 10;
- cur = null;
- }
- return result;
- }
- }
- /**
- DFS + Stack
- Time Complexity: O(n)
- Space Complexity: O(n)
- */
- import javafx.util.Pair;
- class Solution {
- public int sumNumbers(TreeNode root) {
- if (root == null) {
- return 0;
- }
- Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
- stack.push(new Pair<TreeNode, Integer>(root, root.val));
- int result = 0;
- while (!stack.isEmpty()) {
- Pair<TreeNode, Integer> pair = stack.pop();
- if (pair.getKey().left == null && pair.getKey().right == null) {
- result += pair.getValue();
- }
- if (pair.getKey().left != null) {
- TreeNode left = pair.getKey().left;
- int leftVal = pair.getValue() * 10 + left.val;
- stack.push(new Pair<TreeNode, Integer>(left, leftVal));
- }
- if (pair.getKey().right != null) {
- TreeNode right = pair.getKey().right;
- int rightVal = pair.getValue() * 10 + right.val;
- stack.push(new Pair<TreeNode, Integer>(right, rightVal));
- }
- }
- return result;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement