leetcode 199. Binary Tree Right Side View

这个题实际上就是把每一行最右侧的树打印出来，所以实际上还是一个层次遍历。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

依旧利用之前层次遍历的代码，每次大的循环存储的是一行的节点，最后一个节点就是想要的那个节点

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if(root == NULL)
            return result;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            result.push_back(q.back()->val);
            for(int i = q.size();i > 0;i--){
                TreeNode* node = q.front();
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
                q.pop();
            }          
        }
        return result;
    }
};

 

leetcode 116. Populating Next Right Pointers in Each Node

这个题和199题类似，也是层序遍历，且最后一个的node的next为NULL；

class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL)
            return NULL;
        queue<Node*> q;
        q.push(root);
        while(!q.empty()){    
            for(int i = q.size();i > 0;i--){
                Node* node = q.front();
                q.pop();
                if(i != 1)
                    node->next = q.front();
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }         
        }
        return root;
    }
};

 

117. Populating Next Right Pointers in Each Node II

这个题与116不同在于，树不再是完全二叉树。对于递归的方法不同，对于非递归，同一个代码完全可以解决这两个问题

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄