Bloomberg电面

整体感受：

先是指出来一堆错误……
然后用q，又是一堆错误……
醉了。我真的不会写树。
文理学院的白人咋这么聪明啊，或者说对于这道题聪明。我真是被虐得体无完肤了。

忘记一开始就问思路了，因为我就抄了那一种思路T.T
结果还真就错了

整个过程就是面试官教我做题，给我debug
我给cmu丢脸了！

拼写：

广度优先搜索算法（英語：Breadth-First Search，縮寫為BFS）

知识复习：

1.NextNode的定义：下一个同级的树节点

参考：https://docs.microsoft.com/zh-cn/dotnet/api/system.windows.forms.treenode.nextnode?view=net-5.0

这道题跟I的区别就是binary tree不是完全二叉树

2.对于不完全二叉树，没有很一定的性质：root.right.next就不一定等于root.next.left。

3.head/left/right是节点，prev/curr是指针

traverse做错的思考：

写话来表达倒是不错

几个方法都没分清，traverse我说是bfs啊我擦

一开始定义node我就不太会

面经里的prev cur换成了left right，然后我有点懵了
哦，好像是抄错了（微笑）。面试中自己到后面都抄懵逼了
为什么会抄错呢？因为不理解：head/left/right是节点，prev/curr是指针

而且，最好不要在电面（oa也适用）的45分钟之内，尝试去修改答案：动一两个变量然后后面接着改这样。脑子基本转不过来。
要么直接抄，要么自己重新想重新写！

后来就变成他说一步，我写一步。
他告诉我的写法似乎做法有一些道理，但我也不知道错了没错。

q做错的思考：

面经是：加的时候连的

面试官是加完了之后再连的，而且level表示的不是这一层，而是下一层
面试的时候他就一直让我按他的方法做

没抄错，就是要改一点的时候，只有原始模板，没有相对应的答案。所以反应不过来，只顾着抄准备之后改而不是想好了再写，结果被完全纠正了。
下次还是想好了再抄吧，除非一模一样，不要直接抄。

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

//        G                                G                           
//    R       X           ->           R   ->  X                              
//  B   A   C   S                    B -> A   C -> S     

//define a node
Node {
    Character char;
    Node left;
    Node right;
    Node next;
}

//list for a level 
List<> level
//size = q.size();
//for each node in the list, go left, go right and put into queue
//add the first node into the q 
q.offer(root);//g

while (!q.isNull()) {
        Node node = q.poll(); //r
    
    //connect left if not null
    if (node.left != null) {
        level.add(node.left); //level.add(b)
        //add judgement
         
    }
    //right
    if (node.right != null) {
        level.add(node.right);
        //add judgement //evel.add(a)
        
    }
    
    //iterate the level, add node to the queue
    for (int i = 0; i < level.size() - 1; i++) {
        level.get(i).next = level.get(i + 1); //b->a
        q.add(level.get(i));//q.add(b,a)
    }
}

for (int i = 0; i < q.size(); i++) {
    Node node = q.poll();
    level.add(node.val);
    
    //connect left if not null
    if (node.left != null) {
        level.add(node.left);
        node.left.next = node.right; 
    }
    
    //right
    
    //iterate the level, add node to the queue
    for() {
        q.add(level);
    }
    
}

//connect, by level, width first
public void connect(Node root) {
    //define some variables
    Node head = root;
    Node left = null;
    Node right = null;
    int levelFromLeft;
    int levelFromRight;
    
    //bfs
    while (head != null) {
        //initiaze
        curr = head;
        left = null;
        right = null;
        levelFromLeft = 0;
        levelFromRight = 0;
        
        //go to left&right to connect with the right node
        while (curr != null) {
            //go left
            if (curr.left != null) {
                levelFromLeft++; //2
                //connect, check if it has a left node
                //if yes, and right node is not null, let left node connect with right node(on the same level)
                
                //go right
                if (curr.right != null) {
                levelFromRight++;     //2          
                }
                
                //judeg whether levelFromLeft = levelFromRight
                if(levelFromLeft == levelFromRight) {
                    //curr.left.right = curr.right;
                    curr.left.next = curr.right; 
                }
            }
            
            //if curr.left is not null, go left, else go right
            if (curr.left != null) {
                curr = curr.left;
            }else {
                curr = curr.right;
            }
        }
    }
}

整个的草稿

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

//        G                                G                           
//    R       X           ->           R   ->  X                              
//  B   A   C   S                    B -> A   C -> S     

//define a node
Node {
    Character char;
    Node left;
    Node right;
    Node next;
}

//list for a level 
List<> level
//size = q.size();
//for each node in the list, go left, go right and put into queue
//add the first node into the q 
q.offer(root);//g

while (!q.isNull()) {
        Node node = q.poll(); //r
    
    //connect left if not null
    if (node.left != null) {
        level.add(node.left); //level.add(b)
        //add judgement
         
    }
    //right
    if (node.right != null) {
        level.add(node.right);
        //add judgement //evel.add(a)
        
    }
    
    //iterate the level, add node to the queue下一层的都在level中，现在加到q里
    for (int i = 0; i < level.size() - 1; i++) {
        level.get(i).next = level.get(i + 1); //b->a
        q.add(level.get(i));//q.add(b,a)
    }
}
//所有的节点都加到了q之中

for (int i = 0; i < q.size(); i++) {
    Node node = q.poll();
    level.add(node.val);
    
    //connect left if not null
    if (node.left != null) {
　　　　　//这一层从左往右连
        level.add(node.left);
        node.left.next = node.right; 
    }
    
    //right
    
    //iterate the level, add node to the queue
    for() {
　　　　　//然后把这一层加进去
        q.add(level);
    }
    
}

//connect, by level, width first
public void connect(Node root) {
    //define some variables
    Node head = root;
    Node left = null;
    Node right = null;
    int levelFromLeft;
    int levelFromRight;
    
    //bfs
    while (head != null) {
        //initiaze
        curr = head;
        left = null;
        right = null;
        levelFromLeft = 0;
        levelFromRight = 0;
        
        //go to left&right to connect with the right node
        while (curr != null) {
            //go left
            if (curr.left != null) {
                levelFromLeft++; //2
                //connect, check if it has a left node
                //if yes, and right node is not null, let left node connect with right node(on the same level)
                
                //go right
                if (curr.right != null) {
                levelFromRight++;     //2          
                }
                
                //judeg whether levelFromLeft = levelFromRight
                if(levelFromLeft == levelFromRight) {
                    //curr.left.right = curr.right;
                    curr.left.next = curr.right; 
                }
            }
            
            //if curr.left is not null, go left, else go right
            if (curr.left != null) {
                curr = curr.left;
            }else {
                curr = curr.right;
            }
        }
    }
}

相关推荐