Dado un árbol binario y una suma, determine si el árbol tiene una ruta de raíz a hoja tal que la suma de todos los valores a lo largo de la ruta sea igual a la suma dada.
Por ejemplo:
Dado el siguiente árbol binario y suma = 22,
5
/
4 8
/ /
11 13 4
/
7 2 1
devuelve verdadero, ya que existe una ruta de raíz a hoja 5-> 4-> 11-> 2 cuya suma es 22.
Solución 1 de Java: uso de la cola
Agregue todos los nodos a una cola y almacene el valor de la suma de cada nodo en otra cola. Cuando es un nodo hoja, verifique el valor de suma almacenado.
Para el árbol anterior, la cola sería: 5 – 4 – 8 – 11 – 13 – 4 – 7 – 2 – 1. Verificará el nodo 13, 7, 2 y 1. Esta es una primera búsqueda de amplitud típica (BFS) problema.
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root == null) return false; LinkedList<TreeNode> nodes = new LinkedList<TreeNode>(); LinkedList<Integer> values = new LinkedList<Integer>(); nodes.add(root); values.add(root.val); while(!nodes.isEmpty()){ TreeNode curr = nodes.poll(); int sumValue = values.poll(); if(curr.left == null && curr.right == null && sumValue==sum){ return true; } if(curr.left != null){ nodes.add(curr.left); values.add(sumValue+curr.left.val); } if(curr.right != null){ nodes.add(curr.right); values.add(sumValue+curr.right.val); } } return false; } } |
Solución Java 2: recursividad
public boolean hasPathSum(TreeNode root, int sum) { if (root == null) return false; if (root.val == sum && (root.left == null && root.right == null)) return true; return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); } |
¡Gracias a nebulaliang, esta solución es maravillosa!
