数据结构笔记--二叉树经典高频题

1--二叉树的最近公共祖先

主要思路：

最近祖先只有两种情况：① 自底向上，当两个目的结点分别在当前结点的左右子树时，当前结点为两个目的结点的最近祖先；② 最近祖先与其中一个目的结点相同，则另一个目的结点在目的结点的子树上；

递归寻找目的结点，当找到目的结点后往上返回目的结点，否则返回 NULL；当一个结点在左右子树上分别找到了两个目的结点，表明这个结点是最近祖先；否则返回不为空的子树的返回结点（这时两个结点对应第 ② 种情况）；

#include <iostream>
#include <vector>
#include <stack>

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || root->val == p->val || root->val == q->val) return root;

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left != NULL && right != NULL) return root;
        else if( left != NULL) return left;
        else return right;
    }
};

int main(int argc, char *argv[]){

    TreeNode *Node1 = new TreeNode(3);
    TreeNode *Node2 = new TreeNode(5);
    TreeNode *Node3 = new TreeNode(1);
    TreeNode *Node4 = new TreeNode(6);
    TreeNode *Node5 = new TreeNode(2);
    TreeNode *Node6 = new TreeNode(0);
    TreeNode *Node7 = new TreeNode(8);
    TreeNode *Node8 = new TreeNode(7);
    TreeNode *Node9 = new TreeNode(4);

    Node1->left = Node2;
    Node1->right = Node3;
    Node2->left = Node4;
    Node2->right = Node5;
    Node3->left = Node6;
    Node3->right = Node7;
    Node5->left = Node8;
    Node6->right = Node9;

    Solution S1;
    TreeNode* res = S1.lowestCommonAncestor(Node1, Node2, Node9);
    std::cout << res->val << std::endl;

    return 0;
}

2--二叉搜索树的中序后继结点

主要思路：

如果 p 结点有右子树，则返回其右子树最左边的结点（中序遍历的定义）；

如果 p 结点没有右子树，则从 root 结点开始寻找 p 结点的父亲结点；（根据二叉搜索树的定义，可以节省寻找的时间，只需在一边进行寻找）；

#include <iostream>
#include <vector>
#include <stack>


struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode *res = NULL;
        if(p->right != NULL){ // p的中序后继是其右子树上最左的结点（即右字数上最先返回的结点）
            res = p->right;
            while(res->left != NULL) res = res->left;
            return res;
        }

        // p没有右子树，从root结点开始搜索p的父亲结点
        while(root != NULL){
            if(root->val > p->val){ // p在左子树上
                res = root;
                root = root->left; // 在左子树上找到最后一个比p大的结点（中序遍历是有序的，中序后继结点表明是比p结点大）
            }
            else{
                root = root->right; // p在右子树上
            }
        }
        return res;
    }
};

int main(int argc, char *argv[]){

    TreeNode *Node1 = new TreeNode(2);
    TreeNode *Node2 = new TreeNode(1);
    TreeNode *Node3 = new TreeNode(3);

    Node1->left = Node2;
    Node1->right = Node3;

    Solution S1;
    TreeNode* res = S1.inorderSuccessor(Node1, Node2);
    std::cout << res->val << std::endl;

    return 0;
}