二叉树与分治法整理

597. 具有最大平均数的子树

 1 /**
 2  * Definition of TreeNode:
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left, right;
 6  *     public TreeNode(int val) {
 7  *         this.val = val;
 8  *         this.left = this.right = null;
 9  *     }
10  * }
11  */
12 
13 
14 public class Solution {
15     /*
16      * @param root: the root of binary tree
17      * @return: the root of the maximum average of subtree
18      */
19     class Type {
20         int sum;
21         int count;
22         Type(int s, int c) {
23             sum = s;
24             count = c;
25         }
26     }
27     TreeNode res = null;
28     Type max = new Type(0, 0);
29     public TreeNode findSubtree2(TreeNode root) {
30         // write your code here
31         helper(root);
32         return res;
33     }
34     //1. 对于root,返回该节点为根节点的count和sum
35     private Type helper(TreeNode root) {
36         if (root == null) {
37             return new Type(0, 0);
38         }
39         
40         //2.拆解
41         Type left = helper(root.left);
42         Type right = helper(root.right);
43         int sum = left.sum + right.sum + root.val;
44         int count = left.count + right.count + 1; //＋１手误
45         if (res == null || sum * max.count > max.sum * count) {
46             max.count = count;
47             max.sum = sum;
48             res = root;
49         }
50         return new Type(sum, count);　//忘记了
51     }
52 }

View Code

①计算ｓｕｍ时每层＋１②忘记ｈｅｌｐｅｒ返回值。

答案可以更简单一点。

1 if (subtree == null ||
2             subtreeResult.sum * result.size < result.sum * subtreeResult.size
3         ) {
4             subtree = root;
5             subtreeResult = result;
6         }

View Code

93. 平衡二叉树

注意：分治的时候，合并处理时仔细，树的高度要+1。

 1 /**
 2  * Definition of TreeNode:
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left, right;
 6  *     public TreeNode(int val) {
 7  *         this.val = val;
 8  *         this.left = this.right = null;
 9  *     }
10  * }
11  */
12 
13 
14 public class Solution {
15     /*
16      * @param root: The root of binary tree.
17      * @return: True if this Binary tree is Balanced, or false.
18      */
19     class Type {
20         int h;
21         boolean b;
22         Type(int h, boolean b) {
23             this.h = h;
24             this.b = b;
25         }
26     }
27     public boolean isBalanced(TreeNode root) {
28         // write your code here
29         return check(root).b;
30         
31     }
32     private Type check(TreeNode root) {
33         Type res = new Type(0, true);
34         if (root == null) {
35             return res;
36         }
37         
38         
39         Type left = check(root.left);
40         Type right = check(root.right);
41         if (left.b == false || right.b == false || Math.abs(left.h - right.h) > 1) {
42             res.b = false;
43         }
44         res.h = Math.max(left.h, right.h) + 1; //记得+1
45         return res;
46     }
47 }

View Code