The problem link

• 199. Binary Tree Right Side View
• 199. Right view of binary tree

Problem description

Given the root of 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 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Copy the code

Example 2:

Input: root = [1,null,3]
Output: [1,3]
Copy the code

Example 3:

Input: root = []
Output: []
Copy the code

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Their thinking

Idea 1: Recursion

The columns formed in the right view of the binary tree are denoized as V. V1 ~ VhV_1\sim V_hV1 ~ Vh represent the values of each node in the right view from top to bottom, and H is the height of the binary tree. V1V_1V1 must be equal to the value of root. The column table formed by the right view of the left subtree of the binary tree is denoted as LV and the column table formed by the right view of the right subtree is denoted as RV. According to LV and RV, V2 ~ VhV_2\sim V_hV2 ~ Vh can be obtained as follows: Both LV and RV are traversed. If RViRV_iRVi has a value, Vi+1=RViV_{I +1}=RV_iVi+1=RVi; if RViRV_iRVi has no value, LViLV_iLVi is used until the traversal ends.

For example, a binary tree like this:

graph TD
	root((1)) --> t2((2))
	root --> t3((3))
	t2 --> t5((5))
	t2 --> t7((7))
	t3 --> t4((4))
	t3 --> t6((6))
	t5 --> t8((8))
	t5 --> t9((9))

Its root node is 1, LV is [2, 7, 9], RV is [3, 6], then its right view V is equal to [1, 3, 6, 9].

LV can be obtained from the root node of the left subtree, the right view of the left subtree, and the right view of the right subtree of the left subtree. Similarly, RV can be obtained from the root node of the right subtree, the right view of the left subtree, and the right view of the right subtree.

Based on the above ideas, we can write the following recursive code:

public List<Integer> rightSideView(TreeNode root) {
    if (Objects.isNull(root)) {
        return new ArrayList<>();
    }
    List<Integer> rightResult = rightSideView(root.right);
    List<Integer> leftResult = rightSideView(root.left);
    ArrayList<Integer> result = new ArrayList<>(Math.max(rightResult.size(), leftResult.size()) + 1);
    result.add(root.val);
    int i = 0;
    for (; i < rightResult.size(); i++) {
        result.add(rightResult.get(i));
    }
    for (; i < leftResult.size(); i++) {
        result.add(leftResult.get(i));
    }
    return result;
}
Copy the code

The time complexity of this code is not easy to calculate, if you are interested, the space complexity is O(h-1), h is the height of the binary tree.

Idea 2: Hierarchy traversal

Again, if we look at this binary tree, let’s take the nodes at each level and put them in a list and align them right.

graph TD
	root((1)) --> t2((2))
	root --> t3((3))
	t2 --> t5((5))
	t2 --> t7((7))
	t3 --> t4((4))
	t3 --> t6((6))
	t5 --> t8((8))
	t5 --> t9((9))

As you can see, the right view of a binary tree is actually a list of nodes on the right of each level. So, we can go through the binary tree hierarchically, recording the rightmost node of each layer, and finally get the right view of the binary tree. If you are not familiar with binary tree traversal, you can refer to this article: binary tree traversal in detail

The code is as follows:

public List<Integer> rightSideView(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    if (Objects.isNull(root)) {
        return result;
    }
    LinkedList<TreeNode> levelA = new LinkedList<>(), levelB = new LinkedList<>();
    levelA.addFirst(root);
    while(! levelA.isEmpty()) { TreeNode treeNode = levelA.removeLast();if (Objects.nonNull(treeNode.left)) {
            levelB.addFirst(treeNode.left);
        }
        if (Objects.nonNull(treeNode.right)) {
            levelB.addFirst(treeNode.right);
        }
        if(levelA.isEmpty()) { result.add(treeNode.val); LinkedList<TreeNode> tempList = levelB; levelB = levelA; levelA = tempList; }}return result;
}
Copy the code

The code time complexity is O(H2 −1)O(H ^2-1)O(H2 −1), because all nodes of the binary tree are traversed, and in the worst case, the binary tree is a full binary tree with h2− 1H ^2-1 H2 −1; The space complexity is O(2h−1)O(2^{H-1})O(2h−1). Nodes at each layer need to be stored during traversal. The nodes at the last layer of the full binary tree have the largest number of nodes, 2h−12^ H-12h −1. H is the height of the binary tree.

Related topics

Tree, depth-first search, breadth-first search, binary tree