[数据结构与算法]LeetCode刷题——二叉树的右视图#199#Medium

二叉树的右视图的思路探讨与源码
????二叉树的右视图的题目如下图，该题属于树和搜索类型的题目，主要考察对于遍历搜索方法的使用和树结构本身的理解。本文的题目作者想到2种方法，分别是BFS广度优先搜索方法和DFS深度优先搜索方法，其中BFS广度优先搜索方法使用Java进行编写，而DFS深度优先搜索方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。

????本人认为该题目可以使用BFS广度优先搜索方法的思路进行解决，首先初始化最大深度的参数，并且构造一个右视图的Map去保存信息，同时初始化两个队列，一个是存放树节点元素的队列、另一个是保留深度的队列，再把根节点和初始深度0作为值插入到两个队列里面。然后开始循环遍历，首先将两个队列的第一个元素分别弹出，判断节点是否不为空，如果是就比较最大深度值和当前深度值，取更大的那个作为最大深度值，然后将节点的深度信息和节点一起存入右视图的Map里面，再把节点队列尾部分别填充左子节点右又子节点；把深度队列尾部分别填充左子节点和右子节点的深度值，最终直至遍历结束。最后通过循环，获取所有深度值小于最大值的节点，并插入到列表里返回，就是得到了最终的右视图结果。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        int depthMax = -1;
        Map<Integer,Integer> rightResMap = new HashMap<Integer, Integer>();
        Queue<Integer> queueArr = new LinkedList<Integer>();
        Queue<TreeNode> queueTree = new LinkedList<TreeNode>();
        queueArr.add(0);
        queueTree.add(root);

        while (! queueTree.isEmpty()) {
            int depthNum = queueArr.remove();
            TreeNode vertex = queueTree.remove();
            if (vertex != null) {
                depthMax = Math.max(depthNum,depthMax);
                rightResMap.put(depthNum,vertex.val);                
                
                queueTree.offer(vertex.left);
                queueTree.offer(vertex.right);
                queueArr.offer(depthNum + 1);
                queueArr.offer(depthNum + 1);
            }
        }

        List<Integer> resList = new ArrayList<Integer>();
        for (int jr = 0; jr <= depthMax; jr++) {
            resList.add(rightResMap.get(jr));
        }

        return resList;
    }
}

????显然，我们看到BFS广度优先搜索的方法效果还可以，同时还可以使用DFS深度优先搜索方法解决。首先初始化一个最大深度参数和深度字典，并将根节点和它的深度0作为初始值加入到列表里。然后开始遍历这个列表，将列表的元素抛出，如果节点不为空就开始比较最大深度值和当前深度值，再把当前深度值和树节点分别作为KEY和VALUE保存到深度字典里面。并且再列表尾部分别插入左子节点和它的深度以及右子节点和它的深度信息，直到最终遍历结束。然后循环遍历，将不超过最大深度里面的深度字典的值保存到结果列表里，最终返回结果列表即可。所以按照这个思路就可以解决，下面是Python代码：

#喷火龙与水箭龟
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        depthMax=-999
        dictDepth={}
        listTree=[(root,0)]
        while listTree:
            vertex,depthNum=listTree.pop()
            if vertex is not None:
                depthMax=max(depthNum,depthMax)
                dictDepth.setdefault(depthNum,vertex.val)
                listTree.append((vertex.left,depthNum+1))
                listTree.append((vertex.right,depthNum+1))
        resList=[]
        for jr in range(depthMax+1):
            resList.append(dictDepth[jr])
        return resList

????从结果来说Java版本的BFS广度优先搜索方法的效率还可以，而Python版本的DFS深度优先搜索方法的速度也还不错，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。