从根到叶的二进数之和（Java）——算法刷题打卡

从根到叶的二进数之和

//节点的数据结构
  Definition for a binary tree node.
  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;
      }
  }
 

对于此题而言，我们使用深度优先算法来遍历二叉树。

1、深度优先算法是根据二叉树的路径进行遍历
2、广度优先算法是根据二叉树的层级进行遍历

如何针对二叉树的路径进行遍历呢？

• 使用递归，一直向下寻找，直到没有子节点。

• 使用移位运算符来对二进制数转十进制并累加，每找到一个节点，则累加一次。

class Solution {
    int sum = 0;
    public int sumRootToLeaf(TreeNode root) {
        dfs(root,0);
        //取模
        return sum%((int)Math.pow(10,9)+7);
    }
    //dfs算法（递归）
    public void dfs(TreeNode root,int val){
        //非空判断
        if(root==null) return;
        //记录根节点至当前节点的路径的和
        int tmp = (val<<1) + root.val;
        //判断是否存在子节点
        if(root.left != null || root.right != null){
            //存在则递归
            if(root.left!=null){
                dfs(root.left,tmp);
            }
            if(root.right!=null){
                dfs(root.right,tmp);
            }
        }else{
            //否则累加求和
            sum += tmp;
            return;
        }
    }
}