1592: 蓝桥杯算法训练VIP-FBI树

https://www.dotcpp.com/oj/problem1592.html

• 思路

  设当前串为S, 则画图模拟后有:

  • 若S的字符和S.value == S.length; 节点Node=I
  • 若S的字符和S.value == 0; 节点Node = B
  • 此外Node = F

  ---

  上述方法value不如改用统计0/1出现次数, 若能用正则表达式会减少跟多用时与代码量. 可惜我不会, 埃.

  循环\递归以上判断, 循环条件为S.length > 1;

  由于N≤10, 不会产生溢出, 或超时

• 代码

    import java.util.*;
    public class Main {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            Tree T = new Tree();
            scan.nextInt();
            String str = scan.next();
            T.CreatTree(str);
            T.aftOrder();
        }
        static class Tree{
            char c='$';
            Tree LC, RC;
            void CreatTree(String S) {
                int len = S.length();
                //统计0, 1出现次数
                int cnt1=0, cnt0=0;
                for(char ch: S.toCharArray()) 
                    if(ch=='1') cnt1++;
                    else cnt0++;
                if(cnt1==len)
                    this.c = 'I';
                else if(cnt0==len)
                    this.c = 'B';
                else 
                    this.c = 'F';
                if(len>1) {
                    //递归创建左右子树
                    this.LC = new Tree();
                    this.RC = new Tree();
                    this.LC.CreatTree(S.substring(0, len/2));
                    this.RC.CreatTree(S.substring(len/2, len));
                }
                else return;
            }
            void aftOrder() {
                if(this!=null) {
                    if(this.LC!=null)
                        this.LC.aftOrder();
                    if(this.RC!=null)
                        this.RC.aftOrder();
                    System.out.print(this.c);
                }
                return;
            }
        }
    }