leetcode199：二叉树的右视图

题目链接

leetcode

题目描述

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

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -101;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    二叉树的层次遍历：广度优先搜索实现

    对于每一层来说，最右边的结点一定是最后被遍历到的。

    时间复杂度：O(n)
        其中 n 是树中结点的数量。
        每个结点最多进队列一次，出队列一次。
    空间复杂度：O(n)
        每个结点最多进队列一次，所以队列长度最大不超过 n。
*/
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (root == nullptr) return {};

        vector<int> res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int length = q.size();
            for (int i = 0; i < length; i ++) {
                TreeNode* node = q.front(); q.pop();
                if (i == length - 1) res.push_back(node->val);
                if (node->left != nullptr) q.push(node->left);
                if (node->right != nullptr) q.push(node->right);
            }
        }

        return res;
    }
};

/*
    二叉树的深度遍历：深度优先搜索实现

    在搜索过程中，总是先访问右子树。
    对于每一层来说，最右边的结点一定是最后被遍历到的。

    时间复杂度：O(n)
        其中 n 是树中结点的数量。每个结点最多访问一次。
    空间复杂度：O(n)
        最坏情况下，栈空间接近树高度的结点数量，占用 O(n) 空间。
*/
// 递归实现
class Solution_1 {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        dfs(root, 0, res);
        return res;
    }

    void dfs(TreeNode* root, int depth, vector<int>& res) {
        if (root == nullptr) return;
        // 若当前深度大于结果数组的大小，则说明是新一层的最右边结点，将该值加入结果
        if (depth >= res.size()) res.push_back(root->val);
        // 先递归右子树，因为需要找右视图
        dfs(root->right, depth + 1, res);
        dfs(root->left, depth + 1, res);
    }
};
// 迭代实现
class Solution_2 {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> nodeStack;
        stack<int> depthStack;
        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.empty()) {
            TreeNode* node = nodeStack.top(); nodeStack.pop();
            int depth = depthStack.top(); depthStack.pop();
            if (node != nullptr) {
                // 若当前结点的深度不在数组中，则说明在该结点在当前深度下第一个被访问
                if (depth == res.size()) {
                    res.push_back(node->val);
                }
                nodeStack.push(node->left);
                nodeStack.push(node->right);
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }

        return res;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {1, 2, 3, NULL_NODE, 5, NULL_NODE, 4};

    // 创建二叉树
    TreeNode* root = createTree(nums);
    levelOrderTraversal(root);

    // 获取右视图
    vector<int> result = solution.rightSideView(root);
    // 打印结果
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
package main

import "fmt"

// 定义二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 创建二叉树
func createTree(values []int) *TreeNode {
	if len(values) == 0 {
		return nil
	}
	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]

		if i < len(values) && values[i] != -1 {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++

		if i < len(values) && values[i] != -1 {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// 打印二叉树（层序遍历）
func printTree(root *TreeNode) string {
	if root == nil {
		return "[]"
	}
	result := []int{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == nil {
			result = append(result, -1)
			continue
		}
		result = append(result, node.Val)
		queue = append(queue, node.Left)
		queue = append(queue, node.Right)
	}
	// 去掉尾部的 -1
	for len(result) > 0 && result[len(result)-1] == -1 {
		result = result[:len(result)-1]
	}
	return fmt.Sprintf("%v", result)
}

/*
    二叉树的层次遍历，广度优先搜索实现

    对于每一层来说，最右边的结点一定是最后被遍历到的。

    时间复杂度：O(n)
        其中 n 是树中节点的数量。
        每个节点最多进队列一次，出队列一次。
    空间复杂度：O(n)
        每个节点最多进队列一次，所以队列长度最大不超过 n。
*/
func rightSideView(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    res := []int{}
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i ++ {
            node := queue[0]
            queue = queue[1:]
            if i == size - 1 {
                res = append(res, node.Val)
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        } 
    }

    return res
}

/*
    二叉树的深度遍历，深度优先搜索

    在搜索过程中，总是先访问右子树。
    对于每一层来说，最右边的结点一定是最后被遍历到的。

    时间复杂度：O(n)
        其中 n 是树中节点的数量。每个结点最多访问一次。
    空间复杂度：O(n)
        最坏情况下，栈空间接近树高度的结点数量，占用 O(n) 空间。
*/
// 递归实现
var maxDepth int

func rightSideView_1(root *TreeNode) []int {
    maxDepth = 0
    res := []int{}
    dfs(root, 1, &res)
    return res
}

func dfs(node *TreeNode, depth int, res *[]int) {
    if node == nil {
        return
    }
    // 若当前深度大于最大深度，则将该节点的值加入结果
    if depth > maxDepth {
        *res = append(*res, node.Val)
        maxDepth = depth
    }
    // 先递归右子树，保证右子树的节点先被处理
    dfs(node.Right, depth + 1, res)
    dfs(node.Left, depth + 1, res)
}

// 迭代实现
type NodeWithDepth struct {
    Node  *TreeNode
    Depth int
}

func rightSideView_2(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    result := []int{}
    stack := []*NodeWithDepth{{root, 0}}
    depthMap := make(map[int]int)
    for len(stack) > 0 {
        node, depth := stack[len(stack) - 1].Node, stack[len(stack) - 1].Depth
        stack = stack[:len(stack) - 1]

        if _, exists := depthMap[depth]; !exists {
            depthMap[depth] = node.Val
            result = append(result, node.Val)
        }
        if node.Left != nil {
            stack = append(stack, &NodeWithDepth{node.Left, depth + 1})
        }
        if node.Right != nil {
            stack = append(stack, &NodeWithDepth{node.Right, depth + 1})
        }
    }

    return result
}

func main() {
    // 测试用例
    testCases := []struct {
        values   []int
        expected []int
    }{
        {
            values:   []int{1,2,3,-1,5,-1,4},
            expected: []int{1,3,4},
        },
        {
            values:   []int{1,2,3,4,-1,-1,-1,5},
            expected: []int{1,3,4,5},
        },
        {
            values:   []int{1,-1,3},
            expected: []int{1,3},
        },
        {
            values:   []int{},
            expected: []int{},
        },
    }

    for i, tc := range testCases {
        root := createTree(tc.values)
        fmt.Printf("Test Case %d, Input: values = %v\n", i+1, printTree(root))
        result := rightSideView(root)
        resultStr := fmt.Sprintf("%v", result)
        expectedStr := fmt.Sprintf("%v", tc.expected)

        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}
#leetcode
leetcode199：二叉树的右视图
https://lcf163.github.io/2024/04/17/leetcode199：二叉树的右视图/
作者
乘风的小站
发布于
2024年4月17日
许可协议