主要是回溯算法结合树的深度遍历
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int sumNumbers(TreeNode root) { if(root==null){ return 0; } List<TreeNode> root2Leaf = new ArrayList<TreeNode>(); root2Leaf.add(root); int[] sum = new int[1]; backTrack(root, root2Leaf, sum); return sum[0]; } private void backTrack(TreeNode node, List<TreeNode> root2Leaf, int[] sum){ if(node.left==null && node.right==null){ process(root2Leaf, sum); } TreeNode left = node.left; if(left != null){ int size = root2Leaf.size(); root2Leaf.add(left); backTrack(left, root2Leaf, sum); root2Leaf.remove(size); } TreeNode right = node.right; if(right != null){ int size = root2Leaf.size(); root2Leaf.add(right); backTrack(right, root2Leaf, sum); root2Leaf.remove(size); } } private void process(List<TreeNode> root2Leaf, int[] sum){ int d = 0; for(int i=0; i<root2Leaf.size(); i++){ d += (int)Math.pow(10, root2Leaf.size()-i-1) * root2Leaf.get(i).val; } sum[0] += d; } }
相关推荐
javascript js_leetcode题解之129-sum-root-to-leaf-numbers.js
python python_leetcode题解之129_Sum_Root_to_Leaf_Numbers
本文档为LeetCode题解的Java语言实现,涵盖了181页的内容,涉及到数组、链表、树、图、动态规划、回溯算法等多种数据结构和算法。 1. Rotate Array in Java 数组旋转是一个基本的数组操作,要求将数组中的元素旋转...
javascript js_leetcode题解之170-two-sum-iii-data-structure-design.js
javascript js_leetcode题解之167-two-sum-II-input-array-is-sorted.js
java java_leetcode题解之Range Sum Query - Mutable.java
java java_leetcode题解之Range Sum Query - Immutable.java
public void helper(TreeNode root, int level){// 当前层没有 list,新建// 取得当前层的 list迭代pub
c语言入门 c语言_leetcode题解448-find-all-numbers-disappeared-in-an-array.c
c语言入门 C语言_leetcode题解之40-combination-sum-ii.c
javascript js_leetcode题解之113-path-sum-ii.js
js js_leetcode题解之40-combination-sum-II.js
c语言入门 C语言_leetcode题解之39-combination-sum.c
javascript js_leetcode题解之165-compare-version-numbers.js
javascript js_leetcode题解之112-path-sum.js
js js_leetcode题解之39-combination-sum.js
js js_leetcode题解之1-two-sum.js
java java_leetcode-114-flatten-binary-tree-to-linked-list