java - 树的左 View 或右 View

Question

提供树的左/右 View 的有效代码是什么。

例如:-

                                1
                              /   \
     left view--->>          4     7                    <<--right view
                            / \   /
                           3   2  9
                                 /
                                8

这棵树的左 View 是 - 1 4 3 8，右 View 是 - 1 7 9 8

我已经尝试过级别顺序遍历，但是如果树有一些丢失的 child 那么我很难找到级别的起点(在左 View 的情况下)或终点(在右 View 的情况下) , 请给点建议

Answer 1

仅使用单个队列获取左(或右) View 并不困难。将最右边的子节点入队后，在队列中插入“null”作为标志，以标记下一个(子)级别的结束，同时进行级别顺序遍历。

class Node{
    Node left, right;
    int value;
    Node(int value){
        left=right=null;
        this.value = value;
    }
}
public class BinaryTree
{
    Node root;
    public void leftView(){
        //Using single queue.
        boolean leftmost = true;
        if(this.root == null) return;
        Queue<Node> q = new LinkedList<>();
        q.add(this.root);
        q.add(null);
        while(q.isEmpty() == false){
            Node rear = q.poll();
            if(leftmost == true) {
                if(rear == null) break; 
                System.out.print(rear.value + " ");
                leftmost = false;
            }
            if(rear.left != null)  q.add(rear.left);
            if(rear.right != null) q.add(rear.right);
            if(q.peek() == null) {
                leftmost = true;
                q.poll();    //remove it from rear
                q.add(null); //add it at front.
            }
        }
        //OUTPUT : 12 10 25 50
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        BinaryTree bt = new BinaryTree();
        bt.root = new Node(12);
        bt.root.left = new Node(10);
        bt.root.right = new Node(30);
        bt.root.right.left = new Node(25);
        bt.root.right.left.left = new Node(50);
        bt.root.right.right = new Node(40);
        //          12
        //       /     \
        //     10       30
        //            /    \
        //          25      40 
        //         /
        //       50
        bt.leftView();
    }
}