狗哥店面，汗

匿名者 发表于 2020-8-22 04:02
对啊。，要保证每个node要么没有child 要么有两个child

lz你是怎么做的呀？

祝福你過！

zzgzzm 发表于 2020-8-21 23:36
第一问直接用top down 递归应该很容易解。

请问这个删节点的规划具体是怎么定义的？因为只有叶节点为数值 ...

应该只是删除某个subtree之外的所有节点吧，简而言之就是找最大的某个subtree which subtree.val = target

请问是2021 SDE new grad么？网上找不到链接呀？

这题第二问有啥好的办法吗

楼主可以再讲下第2和3问的思路吗？多谢！

1. public class CalcTree {
   
2.     static class TreeNode {
   
3.         String val;
   
4.         TreeNode left;
   
5.         TreeNode right;
   
6.         public TreeNode(String val) {
   
7.             this.val = val;
   
8.             this.left = null;
   
9.             this.right = null;
   
10.         }
    
11.     }
    
12. 
    
13.     TreeNode root;
    
14.     int sum;
    
15.     int deepestDepth;
    
16.     int minNumOfNodesToRemove;
    
17. 
    
18.     public CalcTree(TreeNode root) {
    
19.         this.root = root;
    
20.         this.minNumOfNodesToRemove = Integer.MAX_VALUE;
    
21.     }
    
22. 
    
23.     public int cal() {
    
24.         int res = helper(root);
    
25.         this.sum = res;
    
26.         return res;
    
27.     }
    
28. 
    
29.     public int helper(TreeNode root) {
    
30.         if (root.left == null && root.right == null) {
    
31.             return Integer.parseInt(root.val);
    
32.         }
    
33. 
    
34.         int leftVal = helper(root.left);
    
35.         int rightVal = helper(root.right);
    
36.         if ("+".equals(root.val)) {
    
37.             return leftVal + rightVal;
    
38.         } else {
    
39.             return leftVal - rightVal;
    
40.         }
    
41.     }
    
42.    
    
43.     public int minRemoveToGet(int target) {
    
44.         minNumOfNodesToRemove = Integer.MAX_VALUE;
    
45.         helper2(root, target, 0);
    
46. 
    
47.         return minNumOfNodesToRemove == Integer.MAX_VALUE ? -1 : minNumOfNodesToRemove;
    
48.     }
    
49. 
    
50.     private int helper2(TreeNode node, int target, int depth) {
    
51.         if (node.left == null && node.right == null) {
    
52.             // Based on the description we know it is a full binary tree. So total node number is 2 ^ (deepestDepth + 1) - 1.
    
53.             deepestDepth = depth;
    
54.             return Integer.parseInt(node.val);
    
55.         }
    
56.         int leftVal = helper2(node.left, target, depth + 1);
    
57.         int rightVal = helper2(node.right, target, depth + 1);
    
58. 
    
59.         int res = "+".equals(node.val) ? leftVal + rightVal : leftVal - rightVal;
    
60. 
    
61.         if (res == target) {
    
62.             int height = deepestDepth - depth + 1;
    
63.             int totalNumOfNodes = (int) (Math.pow(2, deepestDepth + 1) - 1);
    
64.             int curNumOfNodes = (int) (Math.pow(2, height) - 1);
    
65.             minNumOfNodesToRemove = Math.min(minNumOfNodesToRemove, totalNumOfNodes - curNumOfNodes);
    
66.         }
    
67. 
    
68.         return res;
    
69.     }
    
70. 
    
71.     public static void main(String[] args) {
    
72.         /**
    
73.          *        +
    
74.          *      +   -
    
75.          *    6  5 4  3
    
76.          */
    
77.         TreeNode node1 = new TreeNode("+");
    
78.         TreeNode node2 = new TreeNode("+");
    
79.         TreeNode node3 = new TreeNode("-");
    
80.         node1.left = node2;
    
81.         node1.right = node3;
    
82.         TreeNode node4 = new TreeNode("6");
    
83.         TreeNode node5 = new TreeNode("5");
    
84.         TreeNode node6 = new TreeNode("4");
    
85.         TreeNode node7 = new TreeNode("3");
    
86.         node2.left = node4;
    
87.         node2.right = node5;
    
88.         node3.left = node6;
    
89.         node3.right = node7;
    
90.         CalcTree solution = new CalcTree(node1);
    
91.         System.out.println(solution.cal());
    
92.         
    
93.         System.out.println(solution.minRemoveToGet(11));
    
94.         System.out.println(solution.minRemoveToGet(1));
    
95.         System.out.println(solution.minRemoveToGet(13));
    
96. 
    
97. 
    
98.     }
    
99. }

复制代码

oumizx 发表于 2020-9-23 19:10
[mw_shl_code=java,true]public class CalcTree {
    static class TreeNode {
        String val;

老哥不一定是完全二叉树吧
         +
      /    \
   -       5
/   \
3   2