求二叉树的各条路径和

系统管理员 2022-05-21 02:17 167阅读 0赞

![这里写图片描述][70]

import java.util.Stack;
     //定义一个二叉树的节点
      class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }
    
    public class Solution {
        public int sumNumbers(TreeNode root) {
            int sum=0;
            if(root==null)
              return sum;
            if(root.left==null&&root.right==null)
              return root.val;
            //深度遍历求二叉树的各条路径的和
           return  preOrderTreeSum(root,sum);
    
        }
    
        public int preOrderTreeSum(TreeNode root,int sum){
              if(root==null)
                 return 0;
               sum=sum*10+root.val;
               if(root.left==null&&root.right==null)
               {
                 return sum;
               }
               //递归调用
               return preOrderTreeSum(root.left,sum)+preOrderTreeSum(root.right,sum);
    
        }
        //二叉树的深度遍历
        public void DeepOrderTree(TreeNode root){
    
              if(root==null)
                 return;
              Stack<TreeNode>stack=new Stack<>();
              stack.push(root);
              if(!stack.isEmpty()){
                   TreeNode node=stack.pop();
                   System.out.println(node.val);
                   if(node.left!=null)
                     DeepOrderTree(node.left);
                   if(node.right!=null)
                     DeepOrderTree(node.right);
              }
        }
    
        public static void main(String[]args){
              TreeNode root=new TreeNode(1);
              root.left=new TreeNode(2);
              root.right=new TreeNode(3);
              Solution s=new Solution();
              s.DeepOrderTree(root);
              System.out.println(s.sumNumbers(root));
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220521/e0e94abb06de49de9240b2904049d824.png
[70 1]: /images/20220521/dd0b1fddec314dc58e1f51742b55b1f7.png