golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-02-20 10:01:12

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) (ans []int) {
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, depth int) {
        if node == nil {
            return
        }
        if depth == len(ans) { // 这个深度首次遇到
            ans = append(ans, node.Val)
        }
        dfs(node.Right, depth+1) // 先递归右子树，保证首次遇到的一定是最右边的节点
        dfs(node.Left, depth+1)
    }
    dfs(root, 0)
    return
}

java 解法, 执行用时: 0 ms, 内存消耗: 41.2 MB, 提交时间: 2024-02-20 09:59:20

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private final List<Integer> ans = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private void dfs(TreeNode root, int depth) {
        if (root == null) return;
        if (depth == ans.size()) // 这个深度首次遇到
            ans.add(root.val);
        dfs(root.right, depth + 1); // 先递归右子树，保证首次遇到的一定是最右边的节点
        dfs(root.left, depth + 1);
    }
}

python3 解法, 执行用时: 26 ms, 内存消耗: 16.4 MB, 提交时间: 2024-02-20 09:59:04

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if node is None: return
            if depth == len(ans):  # 这个深度首次遇到
                ans.append(node.val)
            dfs(node.right, depth + 1)  # 先递归右子树，保证首次遇到的一定是最右边的节点
            dfs(node.left, depth + 1)
        dfs(root, 0)
        return ans

python3 解法, 执行用时: 44 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-18 11:33:31

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
'''
广度优先遍历，
'''
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        rightmost_value_at_depth = dict() # 深度为索引，存放节点的值
        max_depth = -1

        queue = deque([(root, 0)])
        while queue:
            node, depth = queue.popleft()

            if node:
                # 维护二叉树的最大深度
                max_depth = max(max_depth, depth)

                # 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                rightmost_value_at_depth[depth] = node.val

                queue.append((node.left, depth + 1))
                queue.append((node.right, depth + 1))

        return [rightmost_value_at_depth[depth] for depth in range(max_depth + 1)]

python3 解法, 执行用时: 32 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-18 11:31:46

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
'''
我们对树进行深度优先搜索，在搜索过程中，我们总是先访问右子树。
那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。
这样一来，我们可以存储在每个深度访问的第一个结点，
一旦我们知道了树的层数，就可以得到最终的结果数组。
'''
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        rightmost_value_at_depth = dict() # 深度为索引，存放节点的值
        max_depth = -1

        stack = [(root, 0)]
        while stack:
            node, depth = stack.pop()

            if node:
                # 维护二叉树的最大深度
                max_depth = max(max_depth, depth)

                # 如果不存在对应深度的节点我们才插入
                rightmost_value_at_depth.setdefault(depth, node.val)

                stack.append((node.left, depth + 1))
                stack.append((node.right, depth + 1))

        return [rightmost_value_at_depth[depth] for depth in range(max_depth + 1)]