【数据结构刷题专题】—— 二叉树

时间：2024-03-29 12:27:02

二叉树

二叉树刷题框架
在这里插入图片描述
二叉树的定义：

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

1 二叉树的遍历方式

【1】前序遍历

class Solution {
public:
    void traversal(TreeNode* node, vector<int>& vec) {
        if (node == NULL) return;
        vec.push_back(node->val);
        traversal(node->left, vec);
        traversal(node->right, vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

【2】后序遍历

class Solution {
public:
    void traversal(TreeNode* node, vector<int>& vec) {
        if (node == NULL) return;
        traversal(node->left, vec);
        traversal(node->right, vec);
        vec.push_back(node->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

【3】中序遍历

class Solution {
public:
    void traversal(TreeNode* node, vector<int>& vec) {
        if (node == NULL) return;
        traversal(node->left, vec);
        vec.push_back(node->val);
        traversal(node->right, vec);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

【4】层序遍历

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

2 二叉树的属性

【1】101. 对称二叉树

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        if (left != NULL && right == NULL) return false;
        else if (left == NULL && right != NULL) return false;
        else if (left == NULL && right == NULL) return true;
        else if (left->val != right->val) return false;
        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        return outside && inside;
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

【2】104. 二叉树的最大深度
迭代法:

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

递归法：

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

【3】111.二叉树的最小深度
递归法：

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int left = getDepth(node->left);
        int right = getDepth(node->right);
        if (node->left != NULL && node->right == NULL) return 1 + left;
        if (node->left == NULL && node->right != NULL) return 1 + right;
        return 1 + min(left, right);
    }
    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

迭代法：

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if (root == NULL) return 0;
        que.push(root);
        int depth = 0;
        while (!que.empty()) {
            int size = que.size();
            depth++;
            while (size--) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (node->left == NULL && node->right == NULL) return depth;
            }
        }
        return depth;
    }
};

【4】222. 完全二叉树的节点个数
递归法：

class Solution {
public:
    int getNum(TreeNode* node) {
        if (node == NULL) return 0;
        int left = getNum(node->left);
        int right = getNum(node->right);
        return 1 + left + right;
    }
    int countNodes(TreeNode* root) {
        return getNum(root);
    }
};

迭代法：

class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> que;
        if (root == NULL) return 0;
        que.push(root);
        int num = 0;
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* node = que.front();
                que.pop();
                num++;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return num;
    }
};

【5】110. 平衡二叉树

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

【6】257. 二叉树的所有路径

class Solution {
public:
    void traversal(TreeNode* node, string path, vector<string>& result) {
        path += to_string(node->val);
        if (node->left == NULL && node->right == NULL) {
            result.push_back(path);
            return;
        }
        if (node->left) traversal(node->left, path + "->", result);
        if (node->right) traversal(node->right, path + "->", result);
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

【7】404. 左叶子之和

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        int left = sumOfLeftLeaves(root->left);
        if (root->left && root->left->left == NULL && root->left->right == NULL) {
            left = root->left->val;
        }
        int right = sumOfLeftLeaves(root->right);
        return left + right;
    }
};

【8】513. 找树左下角的值
迭代法：

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        que.push(root);
        int val = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == 0) val = node->val;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return val;
    }
};

【9】112. 路径总和

class Solution {
public:
    bool pathSum(TreeNode* node, int count) {
        if (node->left == NULL && node->right == NULL && count == 0) return true;
        if (node->left == NULL && node->right == NULL) return false;
        if (node->left) {
            count -= node->left->val;
            if (pathSum(node->left, count)) return true;
            count += node->left->val;
        }
        if (node->right) {
            count -= node->right->val;
            if (pathSum(node->right, count)) return true;
            count += node->right->val;
        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return false;
        return pathSum(root, targetSum - root->val);
    }
};

【10】543. 二叉树的直径

class Solution {
public:
    int ans;
    int Depth(TreeNode* node) {
        if (node == NULL) return 0;
        int left = Depth(node->left);
        int right = Depth(node->right);
        ans = max(ans, 1 + left + right);
        return 1 + max

相关文章