深度广度优先搜索TreeNode

给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

1.题目

给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

代码语言：javascript复制

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12   13 = 25

代码语言：javascript复制

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495   491   40 = 1026

2.题解

先自定义Node

代码语言：javascript复制

public class TreeNode{
	int val;
    TreeNode left;
    TreeNode right;
    TreeNode(){}
    TreeNode(int val){this.val = val}
    TreeNode(int val,TreeNode left,TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right; 
    }
}

BuildTree

代码语言：javascript复制

public TreeNode createBT(int[] arr,int i){
    if(i>arr.length){
        return null;
    }
    if(arr[i-1] == null){
        return null;
    }
    TreeNode root = new TreeNode(arr[i-1]);
    root.left = createBT(arr,2*i);
    root.right = createBT(arr,2*i 1);
}

1.深度优先搜索

代码语言：javascript复制

class Solution{
    public int sumNumbers(TreeNode root){
        return dfs(root,0);
    }
    
    public int dfs(TreeNode root, int prevSum){
        if(root == null){
            return 0;
        }
        
        int sum = prevSum * 10   root.val;
        if(root.left == null && root.right == null){
            return sum;
        }else{
            return dfs(root.left,sum) dfs(root.right,sum);
        }
    }
}

2.广度优先搜索

代码语言：javascript复制

class Solution{
    public int sumNumbers(TreeNode root){
        if(root == null){
            return 0;
        }
        int sum = 0;
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> numQueue = new LinkedList<Integer>();
        nodeQueue.offer(root);
        numQueue.offer(root.val);
        while(!nodeQueue.isEmpty()){
            TreeNode node = nodeQueue.poll();
            int num = numQueue.poll();
            TreeNode left = node.left,right = node.right;
            if(left == null && right == null){ 
                sum  = num;
            }else{
                if(left != null){
                    nodeQueue.offer(left);
                    numQueue.offer(num * 10   left.val);
                }
                if(right != null){
                    nodeQueue.offer(right);
                    numQueue.offer(num *  right.val);
                }
            }
        }
        return sum;
    }
}

二叉树 int null root 搜索

0 人点赞