LeetCode199之二叉树的右视图(二叉树的深度遍历和广度遍历)[通俗易懂]

题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:

输入: [1,null,3]
输出: [1,3]
示例 3:

输入: []
输出: []

思路分析

深度优先用递归，广度优先用队列

代码实现

方法一（深度优先）

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> rightView = new ArrayList<>();
        dfs(root, 0, rightView);
        return rightView;
    }

    private void dfs(TreeNode node, int depth, List<Integer> rightView) {
        if (node == null) {
            return;
        }

        // 如果当前深度还没有节点被记录，则添加当前节点
        if (depth == rightView.size()) {
            rightView.add(node.val);
        }

        // 首先访问右子节点，然后是左子节点
        dfs(node.right, depth + 1, rightView);
        dfs(node.left, depth + 1, rightView);
    }

 
}

方法二（广度优先，层次遍历）

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) {
            return result;  // 如果根节点为空，则直接返回空列表
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int n = queue.size();
            TreeNode temp = null;

            for (int i = 0; i < n; i++) {
                temp = queue.remove();

                if (temp.left != null) {
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                }
            }

            // 添加每一层的最右边的节点
            if (temp != null) {
                result.add(temp.val);
            }
        }

        return result;
    }
}
       

题目拓展

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {

        if(root==null){
            return "null";
        }

        StringBuilder result = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
 
        while (!queue.isEmpty()) {
            int n = queue.size();

            for (int i = 0; i < n; i++) {
               TreeNode temp = queue.poll();
 
                if (temp != null) {
                    result.append(temp.val + ",");
                    queue.add(temp.left);
                    queue.add(temp.right);
                } else {
                    result.append("null,");
                }
            }
          
  
        }
 
        return result.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        
           
            if (data.equals("null")) {
                return null;
            }

            String[] values = data.split(",");
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode root = new TreeNode(Integer.parseInt(values[0]));
            queue.add(root);

            for (int i = 1; i < values.length; i++) {
                TreeNode parent = queue.poll();

                if (!values[i].equals("null")) {
                    TreeNode left = new TreeNode(Integer.parseInt(values[i]));
                    parent.left = left;
                    queue.add(left);
                }

                // 处理右子节点
                i++;
                if (!values[i].equals("null")) {
                    TreeNode right = new TreeNode(Integer.parseInt(values[i]));
                    parent.right = right;
                    queue.add(right);
                }
            }
        return root;

    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

这道题的技巧是：广度优先遍历的两层循环转化为一层循环

相关题目

LeetCode103二叉树的锯齿形层次遍历(相关话题：二叉树、层次遍历)

LeetCode994腐烂的橘子(相关话题：矩阵dfs和bfs)-CSDN博客

今天的文章LeetCode199之二叉树的右视图(二叉树的深度遍历和广度遍历)[通俗易懂]分享到此就结束了，感谢您的阅读。