剑指offer 54与55


1. 面试题54. 二叉搜索树的第k大节点

method1:中序遍历。

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        if(!root) return -1;
        vector<int> v;
        int number = inOrder(root,v);
        return v[number-k];
    } 
    int inOrder(TreeNode* root,vector<int>& v) {
        int count = 0;
        if(!root) return 0;
        if(root->left) 
            count+=inOrder(root->left,v);
        v.push_back(root->val);
        count++;
        if(root->right) 
            count+=inOrder(root->right,v);
        return count;
    }
};

method2:右根左递归遍历。

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        int res=0;
        int count=0;
        inOrder(root,k,count,res);
        return res;
    } 
    void inOrder(TreeNode* root,int k,int& count,int& res) {

        if(!root) return;

        if(root->right) 
            inOrder(root->right,k,count,res);

        if(++count == k)  {
            res = root->val;
            return;
        }
        if(root->left) 
            inOrder(root->left,k,count,res);
    }
};

method3:右根左迭代遍历。

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        int n=0;
        stack<TreeNode*> s;
        while(root || !s.empty()) {
            while(root) {
                s.push(root);
                root = root->right;
            }
            root = s.top();
            s.pop();
            if(++n == k) return root->val;
            root = root->left;
        }
        return 0;
    } 
};

2.面试题55 - I. 二叉树的深度

method1:递归法。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return 1 + max(maxDepth(root->left),maxDepth(root->right));
    }
};

method2:迭代法。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        int res = 0;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int size = q.size();
            while(size) {
                TreeNode* cur = q.front();
                q.pop();
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);
                size--;
            }
            res++;
        }
        return res;
    }
};

3.面试题55 - II. 平衡二叉树

method1:用负值表示不平衡,避免重复计算。

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return depth(root)>=0;
    }

    int depth(TreeNode* root) {
        if(!root) return 0;
        int l = depth(root->left);
        int r = depth(root->right);

        if(l==-1 || r==-1) return -1;
        if(abs(l-r)>1) return -1;
        return max(l,r) + 1;
    }
};

method2:使用flag标记。

class Solution {
private:
    bool flag{true};
public:
    bool isBalanced(TreeNode* root) {
        depth(root);
        return flag;
    }

    int depth(TreeNode* root) {
        if(!root) return 0;
        int l = depth(root->left);
        int r = depth(root->right);

        if(abs(l-r)>1) 
            flag = false;

        return max(l,r) + 1;
    }
};

更多内容,订阅公众号

文章作者: light-city
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 light-city !
评论
  目录