博文中会简要介绍Leetcode P0199题目分析及解题思路。
“Binary Tree Right Side View”是一道比较有意思的和树结构相关的题目。这道题有两种思路，分别使用广度优先搜索和深度优先搜索的方法实现解题。
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
Input: [1,2,3,null,5,null,4] Output: [1, 3, 4] Explanation: 1 <--- / \ 2 3 <--- \ \ 5 4 <---
首先讲解利用广度优先搜索的解题思路。其实利用广度优先搜索就是在对树进行层遍历，每一层的最右边的结点就是我们从右看这棵树的视图。
我们可以维护两个变量，一个是当前层的结点数目C，另一个是下一层的结点数目N。每当遍历一个结点，就根据其左右孩子结点来增加下一层结点数目N，然后将当前层的结点数目C减去1，若当前层的结点数目C为0时说明当前刚刚遍历过的结点是这一层最右的结点，则记录这个结点的值，然后将下层结点数目N赋值给当前层的结点数目C，并且将N置空即可。
以下是Java的题解代码实现。
/**
* 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 {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> view = new ArrayList<>();
if (root == null)
return view;
Queue<TreeNode> queue = new LinkedList<>();
int numOfNodesInCurrLevel = 1, numOfNodesInNextLevel = 0;
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode curr = queue.poll();
if (curr.left != null) {
++numOfNodesInNextLevel;
queue.offer(curr.left);
}
if (curr.right != null) {
++numOfNodesInNextLevel;
queue.offer(curr.right);
}
--numOfNodesInCurrLevel;
if (numOfNodesInCurrLevel == 0) {
view.add(curr.val);
numOfNodesInCurrLevel = numOfNodesInNextLevel;
numOfNodesInNextLevel = 0;
}
}
return view;
}
}
除了利用广度优先搜索以外，我们还可以使用深度优先搜索。对于一棵树而言，若左右孩子结点均不为空，那么右孩子结点将出现在树的右视图里；若右孩子结点不为空而左孩子结点为空，则右孩子结点会出现在右视图中；若左孩子结点不为空但右孩子结点为空，左孩子结点才会出现在右视图里。
那么根据以上规则，我们可以利用深度优先搜索，并且记录当前遍历到的结点出现的层数。对于每个结点我们判断其出现的层数是否大于当前右视图中的结点值个数，若大于则说明这个结点将出现在右视图里。然后每次我们优先遍历这个结点的右孩子，这样一来对于相同层数的左右孩子结点，总是右孩子结点会先被遍历到，并且进入右视图里。如此递归即可解决问题。
以下是C++的题解代码实现。
/**
* Definition for a binary tree node.
* 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) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
if (!root)
return this->view_;
this->_Dfs(root, 0);
return this->view_;
}
private:
vector<int> view_;
void _Dfs(TreeNode *curr, int level) {
if (level == this->view_.size()) {
this->view_.push_back(curr->val);
}
if (curr->right)
this->_Dfs(curr->right, level+1);
if (curr->left)
this->_Dfs(curr->left, level+1);
}
};