二叉树的右视图

今天药忘吃喽~ 2023-03-01 12:40 1阅读 0赞

# 二叉树的右视图 #

## 1、题目 ##

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

输入: [1,2,3,null,5,null,4]
    输出: [1, 3, 4]
    解释:
    
       1            <---
     /   \
    2     3         <---
     \     \
      5     4       <---

## 2、代码 ##

### 2.1、代码思路 ###

*  大体思路和二叉树的层序遍历差不多，只不过每次只需要当前层的队列中最后一个元素
    
     *  将根节点入队
     *  执行以下操作，直至队列为空
        
         *  将该层的节点的下一层节点依次放入队列中
         *  将该层的最后一个节点从队列中取出，放入待返回的集合中

### 2.2、树节点的定义 ###

//二叉树节点的定义
    class Node {
        
    	public Integer data;
    	public Node left;
    	public Node right;
    
    	public Node(Integer data) {
        
    		this.data = data;
    	}
    
    	public String toString() {
        
    		return data.toString();
    	}
    }

### 2.3、二叉树的右视图 ###

//二叉树的定义
    class BinaryTree {
        
    	public Node root;
    
    	public List<Node> rightSideView() {
        
    		if (root == null) {
        
    			System.out.println("二叉树为空~~~");
    		}
    
    		// 队列
    		Queue<Node> queue = new LinkedList<Node>();
    		// 根节点加入队列
    		queue.add(root);
    
    		// 待返回的集合
    		List<Node> rightSideNodes = new ArrayList<Node>();
    
    		// 循环至队列为空
    		while (!queue.isEmpty()) {
        
    
    			// 当前层的节点个数
    			int curLevelCount = queue.size();
    
    			Node curNode = null;
    
    			// 遍历当前层的节点
    			for (int i = 0; i < curLevelCount; i++) {
        
    				// 依次取出当前层的节点
    				curNode = queue.remove();
    				// 如果其左节点不为空，加入队列中
    				if (curNode.left != null) {
        
    					queue.add(curNode.left);
    				}
    				// 如果其右节点不为空，加入队列中
    				if (curNode.right != null) {
        
    					queue.add(curNode.right);
    				}
    			}
    			// 将当前层最后一个节点加入待返回的集合中
    			rightSideNodes.add(curNode);
    		}
    		return rightSideNodes;
    	}
    }

### 2.4、测试代码 ###

*  代码

public static void main(String[] args) {
        
    
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
    
        // 构造二叉树
        node1.left = node2;
        node1.right = node3;
        node2.left = null;
        node2.right = node5;
        node3.left = null;
        node3.right = node4;
    
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.root = node1;
    
        // 获取二叉树的右视图
        List<Node> rightSideView = binaryTree.rightSideView();
        System.out.println(rightSideView);
    
    }

*  程序运行结果

[1, 3, 4]

### 2.5、全部代码 ###

public class RightSideView {
        
    	public static void main(String[] args) {
        
    
    		Node node1 = new Node(1);
    		Node node2 = new Node(2);
    		Node node3 = new Node(3);
    		Node node4 = new Node(4);
    		Node node5 = new Node(5);
    
    		// 构造二叉树
    		node1.left = node2;
    		node1.right = node3;
    		node2.left = null;
    		node2.right = node5;
    		node3.left = null;
    		node3.right = node4;
    
    		BinaryTree binaryTree = new BinaryTree();
    		binaryTree.root = node1;
    
    		// 获取二叉树的右视图
    		List<Node> rightSideView = binaryTree.rightSideView();
    		System.out.println(rightSideView);
    
    	}
    }
    
    //二叉树的定义
    class BinaryTree {
        
    	public Node root;
    
    	public List<Node> rightSideView() {
        
    		if (root == null) {
        
    			System.out.println("二叉树为空~~~");
    		}
    
    		// 队列
    		Queue<Node> queue = new LinkedList<Node>();
    		// 根节点加入队列
    		queue.add(root);
    
    		// 待返回的集合
    		List<Node> rightSideNodes = new ArrayList<Node>();
    
    		// 循环至队列为空
    		while (!queue.isEmpty()) {
        
    
    			// 当前层的节点个数
    			int curLevelCount = queue.size();
    
    			Node curNode = null;
    
    			// 遍历当前层的节点
    			for (int i = 0; i < curLevelCount; i++) {
        
    				// 依次取出当前层的节点
    				curNode = queue.remove();
    				// 如果其左节点不为空，加入队列中
    				if (curNode.left != null) {
        
    					queue.add(curNode.left);
    				}
    				// 如果其右节点不为空，加入队列中
    				if (curNode.right != null) {
        
    					queue.add(curNode.right);
    				}
    			}
    			// 将当前层最后一个节点加入待返回的集合中
    			rightSideNodes.add(curNode);
    		}
    		return rightSideNodes;
    	}
    }
    
    //二叉树节点的定义
    class Node {
        
    	public Integer data;
    	public Node left;
    	public Node right;
    
    	public Node(Integer data) {
        
    		this.data = data;
    	}
    
    	public String toString() {
        
    		return data.toString();
    	}
    }