剑指Offer之Java算法习题精讲二叉树与N叉树

题目一

 解法

/**
* 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;
*     }
* }
*/
class Solution {
   StringBuffer sb = new StringBuffer();
   List<String> list = new ArrayList<String>();
   public List<String> binaryTreePaths(TreeNode root) {
       method(root);
       return list;
   }
   public void method(TreeNode root){
       if(root==null) return;
       int t = sb.length();
       sb.append(root.val);
       if(root.left==null&&root.right==null){
           list.add(sb.toString());
       }
       sb.append("->");
       method(root.left);
       method(root.right);
       sb.delete(t, sb.length());
   }
}

题目二

 解法

/**
* 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;
*     }
* }
*/
class Solution {
   int ans = 0;
   public int sumOfLeftLeaves(TreeNode root) {
       method(root,false);
       return ans;
   }
   public void method(TreeNode root,boolean flag){
       if(root==null) return;
       if(root.left==null&&root.right==null&&flag){
           ans+=root.val;
           return;
       }
       method(root.left,true);
       method(root.right,false);
   }
}

题目三

 解法

/*
// Definition for a Node.
class Node {
   public int val;
   public List<Node> children;
   public Node() {}
   public Node(int _val) {
       val = _val;
   }
   public Node(int _val, List<Node> _children) {
       val = _val;
       children = _children;
   }
};
*/

class Solution {
   public int maxDepth(Node root) {
       if(root==null){
           return 0;
       }
       int maxChildDepth = 0;
       for(int i = 0;i<root.children.size();i++){
           int childDepth = maxDepth(root.children.get(i));
           maxChildDepth = Math.max(maxChildDepth, childDepth);
       }
       return maxChildDepth+1;
   }
}

来源：https://blog.csdn.net/wai_58934/article/details/123560260