[leetcode] 199. Binary Tree Right Side View

[leetcode] 199. Binary Tree Right Side View

Description

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 <---

分析一

题目的意思是：假设我从右边看二叉树，返回我能看见的二叉树节点，自顶向下输出。

宽度优先搜索的核心就是队列，注意这个解法很常见，这道题的核心就是每次层序遍历返回最后一个值就行了。

代码- BFS

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector rightSideView(TreeNode* root) { vector res; if(!root){ return res; } queue q; q.push(root); TreeNode* t; while(!q.empty()){ int n=q.size(); for(int i=0;ileft){ q.push(t->left); } if(t->right){ q.push(t->right); } } res.push_back(t->val); } return res; }};

分析二

这个DFS的解法可以说是非常的巧妙了，代码很直观，看不懂就模拟一下，核心讲解已经写在代码里面了。

代码二- DFS

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector rightSideView(TreeNode* root) { vector views; scan(root, 0, views); return views; }private: void scan(TreeNode* root, int h, vector& views) { if(!root) return; if(h >= views.size()) views.emplace_back(root->val); /* 先遍历右侧，这样就可以先选择右边的元素 */ scan(root->right, h + 1, views); scan(root->left, h + 1, views); }};

参考文献

​​每天一道LeetCode-----从右向左观察一棵二叉树，返回能看到的元素​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。