其他树

面试题 04.02. 最小高度树

1302. 层数最深叶子节点的和

方法一：递归

• 需要一个变量记录树的最深depth。
• 区分起始点：设置初始maxdep=-1。
• maxdep 小于 depth，为每层第一个点。

class Solution {
    int total=0;
    int maxdep=-1;
public:
    void dfs(TreeNode* root, int depth){
        if(!root) return;
        if(depth>maxdep){
            maxdep=depth;
            total=root->val;
        }
        else if(depth ==maxdep){
            total+= root->val;
        }
        dfs(root->left,depth+1);
        dfs(root->right,depth+1);

    }
    int deepestLeavesSum(TreeNode* root) {
       dfs(root, 0);
       return total;
    }
};

方法二：队列

class Solution {
    int total=0;
    int maxdep=-1;
public:
    int deepestLeavesSum(TreeNode* root) {
       if(!root) return 0;
       queue<TreeNode*> q;
       q.push(root);
       int depth=0;
       while(q.size()>0){
           int n=q.size();
           for(int i=0;i<n;i++){
               TreeNode* temp=q.front();
               q.pop();
               if(depth>maxdep){
                   maxdep=depth;
                   total=temp->val;
               }
               else if(depth==maxdep)
               {
                   total+=temp->val;
               }
               if(temp->left) q.push(temp->left);
               if(temp->right) q.push(temp->right); 
           }
           depth++;
       }
       return total;
    }
};

方法三：还是队列

• 但是不用判断目前深度和最大深度的关系。

class Solution {
public:
    Int deepestLeavesSum (TreeNode* root) {
       if(!root) return 0;
       queue<TreeNode*> q;
       q.push(root);
       int total=0;
       while(q.size()>0){
           int n=q.size();
           total=0;
           for(int i=0;i<n;i++){
               TreeNode* temp=q.front();
               q.pop();
               total+=temp->val;
               if(temp->left) q.push(temp->left);
               if(temp->right) q.push(temp->right); 
           }
       }
       return total;
    }
};

面试题 04.03. 特定深度节点链表

1315. 祖父节点值为偶数的节点和

方法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int val=0;
public:
    void dfs(int grand,int parent ,TreeNode* node){
        if(!node) return;
        if(grand %2 ==0) val+=node->val;
        if(node->left) dfs(parent, node->val, node->left);
        if(node->right) dfs(parent, node->val, node->right);
    }
    int sumEvenGrandparent(TreeNode* root) {
      dfs(1,1,root);
      return val;
    }
};

方法二：队列

class Solution {
    int val=0;
public:
    int sumEvenGrandparent(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()){
            int n = q.size();
            for(int i=0;i<n;i++){
                TreeNode* temp=q.front();
                q.pop();
                if(temp->val %2 ==0){
                    if(temp->left){
                        if(temp->left->left)
                            val+=temp->left->left->val;
                        if(temp->left->right)
                            val+=temp->left->right->val;
                    }
                    if(temp->right){
                        if(temp->right->left)
                            val+=temp->right->left->val;
                        if(temp->right->right)
                        val+=temp->right->right->val;
                    }
                }
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);
            }
        }
        return val;
    }
};