狗哥店面，汗

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

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

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

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. }

复制代码

第一问应该是个post-order traversal就可以了
第二问 没有想到什么特别好的方法。。。同问一下删除的规则是怎么样的如果给的树是
        -
   -         +
1    +   3  4
  -5    6

原来的表达式是1 - (-5 +6）- (3 + 4)
可以只把6删除了吗？还是必须要把1，-5，6都给删除了

请问"二叉树组成的表达式"指的是什么呢？

djw612 发表于 2020-08-21 07:50:35
请问"二叉树组成的表达式"指的是什么呢？

这个题是以二叉树的形式来表达一个串连的binary operations.

叶节点为input values, 非叶节点为binary operators (+ or -).

第一问直接用top down 递归应该很容易解。

请问这个删节点的规划具体是怎么定义的？因为只有叶节点为数值，那么究竟怎么删才能保持“剩余”的树仍然是个合法的表达式？

请问楼主投的是什么岗位呀

旧未来 发表于 2020-8-21 23:48
第一问应该是个post-order traversal就可以了
第二问 没有想到什么特别好的方法。。。同问一下删除的规则 ...

按对于子节点数量的要求，删6肯定得删5，那剩一个加号算什么：(1 - (+)) - (3 + 4), 当0处理吗？题目没有表达清楚

匿名者 发表于 2020-8-22 03:41
删5，删6，然后把加号替换成6.

还是有点confuse, 如果是删除1呢？是变成这个样子吗？
        -
   +         +
-5   6   3  4