给定一棵二叉树,返回其右视图列表:即从二叉树右侧看过去,从上到下每层看到的最右边的值的数组。需要实现的函数头如下:
vector<int> rightView(TreeNode* root); TreeNode定义如下: class TreeNode { TreeNode *left, *right; int val; }; Input:[5, 6, 9, null, null, 7, 8] (层次遍历表示法) Output:[5, 9, 8]
private ArrayList<Integer> rightSideView(TreeNode root){ ArrayList<Integer> viewList = new ArrayList<>(); if(root == null) return viewList; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while(!queue.isEmpty()){ int queueLength = queue.size(); for(int i = 0; i < queueLength; i++){ TreeNode node = queue.poll(); if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); if(i == queueLength - 1) viewList.add(node.val); } } return viewList; }采用宽度优先搜索,每次保存每一层树的最后一个节点即可
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; /** 这道题 因为input输入 所以把整套流程实现一下 */ public class Tree<T> { private TreeNode<T> root ; public Tree(){ this.root = null; } public Tree(T[] value){ this.root = getTree(value); } private TreeNode<T> getTree(T[] value){ TreeNode<T> p = new TreeNode<>(value[0]); TreeNode<T> q = p; Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>(); int i=0; while (p!=null){ if(2*i+1<value.length){ p.left = new TreeNode<>(value[2*i+1]); queue.add(p.left); } if (2*i+2<value.length){ p.right = new TreeNode<>(value[2*i+2]); queue.add(p.right); } p = queue.poll(); i+=1; } return q; } /** * 层次遍历 */ public void getSort(TreeNode<T> p){ Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>(); while (p!=null){ System.out.print(p.getValue().toString()+" "); if(p.left!=null){ queue.add(p.left); } if(p.right!=null){ queue.add(p.right); } p = queue.poll(); } } /** 关键目标函数 也是使用层次遍历的思想 遍历的第1/3/7/15....2N-1项即为目标 */ public ArrayList getSolution(TreeNode<T> p){ Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>(); ArrayList list = new ArrayList(); int i=1; while (p!=null){ if(isG(i)){ list.add(p.getValue()); } i++; if(p.left!=null){ queue.add(p.left); } if(p.right!=null){ queue.add(p.right); } p = queue.poll(); } return list; } /*判断 如果是层次遍历的话 遍历的第1/3/7/15....2N-1项即为目标,这里判断i是否符合*/ private static int n =2; public static boolean isG(int i){ if(i==n-1&&i!=0){ n=n*2; return true; }else return false; } public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String str = bf.readLine(); bf.close(); String[] value = str.substring(1,str.length()-1).split("\\,"); // System.out.println(Arrays.toString(value)); Tree<String> tree = new Tree<String>(value); //tree.getSort(tree.root); //System.out.println(); System.out.println(tree.getSolution(tree.root).toString()); // for(int i=0;i<10;i++){ // if(isG(i)){ // System.out.println(i); // } //} } }
public class RightView { List<Integer> list = new ArrayList<>(); private int[] recurse(Node root) { if (root == null) { return switchIntArray(list); } list.add(root.val); if (root.right != null) { return recurse(root.right); } else if (root.left != null) { return recurse(root.left); } else { return switchIntArray(list); } } class Node{ Node left,right; int val; Node(int val) { this.val = val; } } private int[] switchIntArray(List<Integer> list) { int[] array = new int[list.size()]; for(int i = 0;i<list.size();i++){ array[i] = list.get(i); } return array; } }
#include<iostream> #include<vector> #include<queue> using namespace std; vector<int> rightView(TreeNode* root){ vector<int> ans; if(!root)return ans; queue<TreeNode*> q; q.push(root); while(!q.empty()){ int n = q.size(); for(int i = 0; i < n; i++){ TreeNode* tmp = q.front(); q.pop(); if(i == 0)ans.emplace_back(tmp->val); if(tmp->right)q.push(tmp->right); if(tmp->left)q.push(tmp->left); } } return ans; }
// simple level-order traversal public int[] rightView(TreeNode root) { List<Integer> ans = new ArrayList<>(); Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { int size = q.size(); while (size-- > 0) { TreeNode cur = q.poll(); if (cur.left != null) q.offer(cur.left); if (cur.right != null) q.offer(cur.right); } ans.add(cur.val); } int out = new int[ans.size()]; int i = 0; for (int n : ans) { out[i++] = n; } return out; }
if(root==NULL) return NULL; TreeNode* tree=root; vector<int> res; while(tree!=NULL) { if(tree->right!=NULL) {res.push(tree->rigth->val); tree=tree->right;} else {if(tree->left!=NULL) {res.push_back(tree->left->val); tree=tree->left;} else return res;
}
}
public class Main { private static class Node { int data; Node left; Node right; public Node(int data) { this.data = data; } } public static Object[] getRightNumber(Node node) { if (node == null) { return null; } List<Integer> result = new ArrayList<>(); Stack<Node> stack = new Stack<>(); stack.push(node); while (!stack.isEmpty()) { Node temp = stack.pop(); result.add(temp.data); if (temp.right != null) { stack.push(temp.right); } } return result.toArray(); } public static void main(String[] args) { Node node1 = new Node(5); Node node2 = new Node(6); Node node3 = new Node(9); node1.left = node2; node1.right = node3; Node node4 = new Node(7); Node node5 = new Node(8); node3.left = node4; node3.right = node5; System.out.println(Arrays.toString(getRightNumber(node1))); } }