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 <---
A:
我所能想到的,就是简单的bfs (dfs)
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> list = new LinkedList<Integer>(); Queue<TreeNode> queue = new LinkedList(); if(root == null) return list; queue.add(root); while( queue.isEmpty() == false){ Queue<TreeNode> newQueue = new LinkedList(); boolean isFirst = true; while( ! queue.isEmpty()){ TreeNode node = queue.poll(); if(isFirst){ list.add(node.val); isFirst = false; } if(node.right != null) newQueue.add(node.right); if(node.left != null) newQueue.add(node.left); } queue = newQueue; } return list; } }
***********dfs ****************
/** * 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) { vector<int> res; helper(root, 1, res); return res; } private: void helper(TreeNode * root, int depth, vector<int> & res){ if(!root) return; if(res.size() < depth){ res.push_back(root->val); } helper(root->right, depth+1, res); helper(root->left, depth+1, res); } };
Mistakes:
Learned:
No comments:
Post a Comment