[数据结构与算法]专题复习：二叉树（3）

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

对于二叉搜索树而言，因为其特殊的结构，即左子树的值均小于root的值，右子树的值均大于root的值，因此，对于二叉搜索树的最近公共祖先比较好确定。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return root;

        if(p->val == root->val || q->val == root->val)//如果p和q其中一个等于root 那么root即为最近公共祖先
        {
            return root;
        }
        if(p->val < root->val && q->val < root->val)// 如果p和q的值都小于root的值那么去root的左子树去寻找
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if(p->val > root->val && q->val > root->val)// 如果p和q的值都大于root的值那么去root的右边子树去寻找
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        else //此时说明 p和q位于root的左右两侧
        {
            return root;
        }
        
    }
};

剑指 Offer 68 - II. 二叉树的最近公共祖先

二叉树不像二叉搜索树那样结构与数值大小强相关。因此，不同通过判断p->val q->val和root->val的值的关系去选择去root->left或者root->right找最近公共祖先，只能分别试着去root->left或者root->right找最近公共祖先，如果其中一个为空，则返回另一个，如果两个都为空 返回空，如果两个均不为空，那么返回此时的root

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return root;
        if(p->val == root->val || q->val == root->val) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q); 
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if(!left) return right;
        else if(!right) return left;
        else return root;
    }
};

leetcode?662. 二叉树最大宽度

思路：利用满二叉树? BFS

?我们可以把这些值存在原来的节点中，也可以新建一个map来保存这些值。

并利用双端队列deque

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        int len = 0;
        deque<TreeNode*> a;
        root->val = 1;
        a.push_back(root);

        while(!a.empty())
        {
            int size = a.size();
            len = max(len, a.back()->val - a.front()->val + 1);
            // 编号缩小的差值
            int offset = a.front()->val;//为了防止节点中的val过大
                                        //二叉树中每一行的第一个节点中的值，作为参考值 去计算后面节点的值
            while(size--)
            {
                TreeNode* temp = a.front();
                temp->val -= offset;
                a.pop_front();
                if(temp->left)
                {
                    a.push_back(temp->left);
                    temp->left->val = 2 * temp->val;
                }
                if(temp->right)
                {
                    a.push_back(temp->right);
                    temp->right->val = 2 * temp->val + 1;
                }
                
            }
        }
        return len;
    }
};

剑指 Offer 54. 二叉搜索树的第k大节点

思路：采用右--中--左的遍历方式

注意：count++之后立即进行判断是否是第k大的数? count记录第count个大的值

class Solution {
    int res = 0;
    void dfs(TreeNode* root, int k, int &count)
    {
        if(!root) return;       
        if(root->right) dfs(root->right, k, count);
        count++;
        if(count == k) 
        {
            res = root->val;
            return;
        }
        if(root->left) dfs(root->left,k, count);      
    }
public:
    int kthLargest(TreeNode* root, int k) {
        if(!root) return 0;
        int count = 0;
        dfs(root, k, count);
        return res;
    }
};

leetcode?230. 二叉搜索树中第K小的元素

思路：同上

class Solution {

    int res = 0;
    void dfs(TreeNode* root, int k, int& count)
    {
        if(!root) return;
        dfs(root->left, k , count);
        count++;
        if(count == k)
        {
            res = root->val;
            return;
        }
        dfs(root->right, k , count);
    }
public:
    int kthSmallest(TreeNode* root, int k) {
        if(!root) return 0;
        int count = 0;
        dfs(root, k ,count);
        return res;
    }
};

剑指 Offer 55 - II. 平衡二叉树

思路：根据求二叉树的最大深度 只需要加个比较 left和right的差值

class Solution {
    bool res = true;
    int dfs(TreeNode *root)
    {
        if(!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        if(abs(left - right) > 1)
        {
            res = false;
            return 0;
        }
        return max(left, right) + 1;
    }
public:
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return res;
    }
};