leetcode199.二叉树的右视图

题目链接

给定一个二叉树

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

试想象自己站在右侧，返回从右侧所能看到的节点值，即:

[1, 3, 4]

思路一：recursion

递归的思路其实非常简单，对于一棵二叉树，定义根节点为root;如果root.left != null && root.right != null那么就要考虑两种情况即：

1. 左子树的高度高于右子树
2. 右子树的高度大于等于左子树

针对情况1来说：

   1            
 /   \
2     3         
 \     \
  5     4
 /
6      

返回的结果为：节点root + 右子树的右视图 + 左子树高度大于右子树部分的右视图

针对情况2来说：
返回的结果为：节点root + 右子树的右视图 即可。

除了对root.left != null && root.right != null进行分析，还需要对各种情况去分析，这里就不一一罗列了，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null){
            return new ArrayList<Integer>();
        }
        if(root.left != null && root.right != null){
            List<Integer> lRightSideView = rightSideView(root.left);
            List<Integer> rRightSideView = rightSideView(root.right);

            if(lRightSideView.size() > rRightSideView.size()){
                List<Integer> res = new ArrayList<>();
                res.add(root.val);
                int i = 0;
                for(;i < rRightSideView.size();++i){
                    res.add(rRightSideView.get(i));
                } 
                for(;i < lRightSideView.size();++i){
                    res.add(lRightSideView.get(i));
                }
                return res;
            }else{
                List<Integer> res = new ArrayList<>();
                res.add(root.val);
                res.addAll(rRightSideView);
                return res;
            }

        }else if(root.left != null && root.right == null){
            List<Integer> lRightSideView = rightSideView(root.left);
            List<Integer> res = new ArrayList<>();
            res.add(root.val);
            res.addAll(lRightSideView);
            return res;
        }else if(root.left == null && root.right != null){
            List<Integer> rRightSideView = rightSideView(root.right);
            List<Integer> res = new ArrayList<>();
            res.add(root.val);
            res.addAll(rRightSideView);
            return res;
        }else{
            List<Integer> res = new ArrayList<>();
            res.add(root.val);
            return res;
        }
    }
}

时间复杂度：O(N),因为我们需要遍历到二叉树的每一个节点
额外空间复杂度：最差的情况为递归深度为N,此时的额外空间复杂度为O(N)

代码执行结果：

思路二：BFS

广度优先遍历其实无非就是层序遍历，二叉树的层序遍历我们应用到了队列，右视图问题就是在层序遍历遍历到每一层最后一个节点时，将最后一个节点保存即可，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; ++i){
                
                root = queue.poll();

                if(root.left != null){
                    queue.offer(root.left);
                }
                if(root.right != null){
                    queue.offer(root.right);
                }
                if(i == size - 1){
                    res.add(root.val);
                }
            }
        }
        return res;
    }
}

时间复杂度：O(N)
额外空间复杂度：O(N);因为每个节点最多进出队列一次，所以最多消耗的队列长度即二叉树的节点总数N
代码执行结果如下：

思路三：DFS

深度优先：DFS
首先，思考下二叉树的先序遍历，二叉树的先序遍历原则是：

根节点->左子树->右子树

其实不难发现二叉树先序遍历我们访问的节点顺序就是二叉树的左视图。所以，如果想得到二叉树右视图，我们只需要按照：

根节点->右子树->左子树

这样的顺序来进行访问即可，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> res = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root,0);
        return res;
    }

    private void dfs(TreeNode root,int level){
        if(root == null){
            return;
        }
        if(res.size() == level){
            res.add(root.val);
        }
        level++;
        dfs(root.right,level);
        dfs(root.left,level);
    }
}

时间复杂度：O(N)
额外空间复杂度：O(N),最好的情况下，对一棵平衡二叉树而言，递归栈的深度为logN,最差的情况下退化为N,所以额外空间复杂度为O(N)

执行结果：