二叉树45度视角可见节点求解：非对角线视图问题

Great question! Let's break down how to solve this problem step by step, based on your example and visibility rules:

• Nodes on the same 45-degree diagonal (running from bottom-left to top-right) overlap.
• Deeper nodes (lower in the tree) block shallower nodes above them on the same diagonal.
• For nodes at the same depth on the same diagonal, right-subtree nodes block left-subtree nodes.
• Adding a child to node 6 blocks node 7, meaning deeper nodes on the same diagonal always take precedence.

Core Idea #

We can map each node to a diagonal key that groups nodes lying on the same 45-degree line. For this problem, the key is calculated as depth + horizontal_position, where:

• depth is the level of the node (root = 0, its children = 1, etc.)
• horizontal_position is the horizontal offset from the root (root = 0, left children = parent position - 1, right children = parent position + 1)

We traverse the tree with a right-first priority (to ensure right-subtree nodes are recorded before left-subtree nodes at the same depth) and track the deepest node for each diagonal key.

Implementation Steps #

1. Define the Tree Node Structure #

First, use a standard binary tree node class:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

2. Recursive DFS Solution #

We'll use a dictionary to store the deepest node for each diagonal key, then sort the results by key to get the final visible nodes.

def get_45_degree_visible_nodes(root):
    visible_nodes = {}  # key: diagonal key, value: (depth, node value)

    def dfs(node, depth, pos):
        if not node:
            return
        
        diagonal_key = depth + pos
        # Update the entry only if the current node is deeper than the existing one
        if diagonal_key not in visible_nodes or depth > visible_nodes[diagonal_key][0]:
            visible_nodes[diagonal_key] = (depth, node.val)
        
        # Traverse right subtree first to prioritize right nodes at the same depth
        dfs(node.right, depth + 1, pos + 1)
        dfs(node.left, depth + 1, pos - 1)

    dfs(root, 0, 0)
    # Sort the diagonal keys and extract the visible node values
    sorted_keys = sorted(visible_nodes.keys())
    return [visible_nodes[key][1] for key in sorted_keys]

3. Iterative DFS Solution (Avoid Recursion Limits) #

For very deep trees, an iterative approach using a stack avoids recursion depth issues:

def get_45_degree_visible_nodes(root):
    if not root:
        return []
    
    visible_nodes = {}
    # Stack stores tuples of (node, depth, horizontal position)
    stack = [(root, 0, 0)]

    while stack:
        node, depth, pos = stack.pop()
        diagonal_key = depth + pos

        if diagonal_key not in visible_nodes or depth > visible_nodes[diagonal_key][0]:
            visible_nodes[diagonal_key] = (depth, node.val)
        
        # Stack is LIFO: push left first so right is processed first
        if node.left:
            stack.append((node.left, depth + 1, pos - 1))
        if node.right:
            stack.append((node.right, depth + 1, pos + 1))
    
    sorted_keys = sorted(visible_nodes.keys())
    return [visible_nodes[key][1] for key in sorted_keys]

Testing the Solution #

Let's test with your example tree:

# Build the example tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# Get visible nodes
print(get_45_degree_visible_nodes(root))  # Output: [4, 6, 7]

If we add a right child to node 6:

root.right.left.right = TreeNode(8)
print(get_45_degree_visible_nodes(root))  # Output: [4, 6, 8]

This matches your description where the new node blocks 7.

Why This Works #

• Diagonal Key: depth + pos correctly groups nodes on the same 45-degree line.
• Right-First Traversal: Ensures that right-subtree nodes are recorded before left-subtree nodes at the same depth, so they aren't overwritten.
• Depth Priority: Deeper nodes always replace shallower ones on the same diagonal, as they block the nodes above them.

内容的提问来源于stack exchange，提问作者Gurinder