Dado un árbol binario que contiene dígitos del 0 al 9 únicamente, cada ruta de raíz a hoja podría representar un número. Encuentre la suma total de todos los números de raíz a hoja.
Por ejemplo,
1 / 2 3
La ruta de raíz a hoja 1-> 2 representa el número 12.
La ruta de raíz a hoja 1-> 3 representa el número 13.
Devuelve la suma = 12 + 13 = 25.
Solución Java – Recursiva
Este problema puede resolverse con un enfoque DFS típico.
public int sumNumbers(TreeNode root) { int result = 0; if(root==null) return result; ArrayList<ArrayList<TreeNode>> all = new ArrayList<ArrayList<TreeNode>>(); ArrayList<TreeNode> l = new ArrayList<TreeNode>(); l.add(root); dfs(root, l, all); for(ArrayList<TreeNode> a: all){ StringBuilder sb = new StringBuilder(); for(TreeNode n: a){ sb.append(String.valueOf(n.val)); } int currValue = Integer.valueOf(sb.toString()); result = result + currValue; } return result; } public void dfs(TreeNode n, ArrayList<TreeNode> l, ArrayList<ArrayList<TreeNode>> all){ if(n.left==null && n.right==null){ ArrayList<TreeNode> t = new ArrayList<TreeNode>(); t.addAll(l); all.add(t); } if(n.left!=null){ l.add(n.left); dfs(n.left, l, all); l.remove(l.size()-1); } if(n.right!=null){ l.add(n.right); dfs(n.right, l, all); l.remove(l.size()-1); } } |
Mismo enfoque, pero estilo de codificación más simple.
public int sumNumbers(TreeNode root) { if(root == null) return 0; return dfs(root, 0, 0); } public int dfs(TreeNode node, int num, int sum){ if(node == null) return sum; num = num*10 + node.val; // leaf if(node.left == null && node.right == null) { sum += num; return sum; } // left subtree + right subtree sum = dfs(node.left, num, sum) + dfs(node.right, num, sum); return sum; } |
