DFS
时间复杂度:o(N),空间复杂度:o(N)。
用两个栈来储存节点和节点值,节点是为了取到他的左右节点来形成联系,就是说你要知道他的子节点你就必须通过父节点来找到它。值的话就是我们要的结果。
代码如下:
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public int sumNumbers (TreeNode root){ // write code here if(root==null) return 0; Stack<TreeNode> nodeStack=new Stack<>(); Stack<Integer> valueStack=new Stack<>(); int res=0; nodeStack.add(root); valueStack.add(root.val); while(!nodeStack.isEmpty()){ TreeNode node=nodeStack.pop(); int value=valueStack.pop(); if(node.left==null&&node.right==null){ res+=value; }else{ if(node.left!=null){ nodeStack.push(node.left); valueStack.push(value*10+node.left.val); } if(node.right!=null){ nodeStack.push(node.right); valueStack.push(value*10+node.right.val); } } } return res; } }