199. Right view of binary trees

Make writing a habit together! This is the fourth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Topic describes

Given the root node of a binary tree, root, imagine yourself standing on the right side of it and returning the values of the nodes visible from the right side, in order from top to bottom.

Thought analysis

We can only see from the graph that the priority of the right subtree is greater than that of the left subtree. Therefore, we can consider traversing the left subtree by the root node – “right subtree -“. If the traversal of the right subtree is successful, the left subtree is not traversed.

When it came to implementation, I was thinking about recursion at first, but then I realized that a while loop would work

vector<int> rightSideView(TreeNode* root) {
        TreeNode* tmp = root;
        vector<int> ret;
        while(tmp ! =nullptr) {
            ret.push_back(tmp -> val);
            if(tmp -> right ! =nullptr){
                tmp = tmp -> right;
            }else{ tmp = tmp -> left; }}return ret;
    }
Copy the code

However, this is not the case, there will be left subtree deep, so the more appropriate thinking is actually hierarchical traversal

This is also more like a test of our difficulty

One area of hierarchical traversal that I didn’t have a good grasp of is how hierarchical traversal distinguishes each layer. After reading the solution, I learned that when traversing, I first get the length of the queue, and then nest a for loop.

The rightmost node of each layer can also be obtained in this way.

conclusion

So, going back to the idea that breadth-first traversal is possible, depth-first traversal should also be possible, because after all, it’s traversal of all nodes.

In fact, the idea is to constantly find the rightmost node, but the path is only a line, let’s think about the premise of a depth traversal, whether to determine the rightmost node of each layer?

Sure, just get the number of layers as you traverse each node, and add to the array if the number of layers is greater than arr.size().