[LeetCode] 二叉树相关题目（不完全）

最近在做LeetCode上面有关二叉树的题目，这篇博客仅用来记录这些题目的代码。

二叉树的题目，一般都是利用递归来解决的，因此这一类题目对理解递归很有帮助。

1.Symmetric Tree（https://leetcode.com/problems/symmetric-tree/description/）

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

2.Binary Tree Level Order Traversal（https://leetcode.com/problems/binary-tree-level-order-traversal/description/）

class Solution {public:    vector<vector<int>> levelOrder(TreeNode* root) {        vector<vector<int>> res;        if (root == NULL) return res;        queue<TreeNode*> q;        q.push(root);        while (!q.empty()) {            int layer_size = q.size();            vector<int> layer;            for (int i = ; i < layer_size; i++) {                TreeNode *temp = q.front();                q.pop();                layer.push_back(temp->val);                if (temp->left != NULL) q.push(temp->left);                if (temp->right != NULL) q.push(temp->right)；            }                    }        return res;    }};

3.Binary Tree Level Order Traversal II（https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/）

class Solution {public:    vector<vector<int>> levelOrderBottom(TreeNode* root) {        vector<vector<int>> res;        if (root == NULL) return res;        vector<int> layer;        queue<TreeNode*> q;        q.push(root);        int count = ;        while (!q.empty()) {            TreeNode* temp = q.front();            q.pop();            count--;            layer.push_back(temp->val);            if (temp->left != NULL) q.push(temp->left);            if (temp->right != NULL) q.push(temp->right);            if (count == ) {                count = q.size();                res.push_back(layer);                layer.clear();            }        }        for (int i = ; i < res.size() / ; i++) {            vector<int> temp = res[i];            res[i] = res[res.size() - i - ];            res[res.size() - i - ] = temp;        }        return res;    }};

4.Same Tree（https://leetcode.com/problems/same-tree/description/）

class Solution {public:    bool isSameTree(TreeNode* p, TreeNode* q) {        if (p == NULL && q == NULL) return true;        if (p == NULL || q == NULL) return false;        if (p->val != q->val) return false;        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);    }};

5.Path Sum（https://leetcode.com/problems/path-sum/description/）

class Solution {public:    bool hasPathSum(TreeNode* root, int sum) {        if (root == NULL) return false;        if (root->left == NULL && root->right == NULL && sum == root->val) return true;        else return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);    }};

6.Path Sum II（https://leetcode.com/problems/path-sum-ii/description/）

class Solution {public:     void helper(TreeNode *root, vector<vector<int>>& res, vector<int> t, int sum) {        if (root == NULL) return;        if (sum - root->val ==  && root->left == NULL && root->right == NULL) {            t.push_back(root->val);            res.push_back(t);        }         else if (root->left == NULL && root->right == NULL) {             return;         }        else {            t.push_back(root->val);            helper(root->left, res, t, sum - root->val);            helper(root->right, res, t, sum - root->val);        }    }    vector<vector<int>> pathSum(TreeNode* root, int sum) {        vector<vector<int>> res;        if (root == NULL) return res;        vector<int> t;        helper(root, res, t, sum);        return res;    }};

7.Sum Root to Leaf Numbers（https://leetcode.com/problems/sum-root-to-leaf-numbers/description/）

class Solution {public:    int sumNumbers(TreeNode* root) {        return helper(root, );    }    int helper(TreeNode *root, int sum) {        if (root == NULL) return ;        if (root->left == NULL && root->right == NULL) return sum *  + root->val;        else return helper(root->left, sum *  + root->val ) + helper(root->right, sum *  + root->val);    }};

8.Binary Tree Right Side View（https://leetcode.com/problems/binary-tree-right-side-view/description/）

class Solution {public:    vector<int> rightSideView(TreeNode* root) {        vector<int> res;        if (root == NULL) return res;        queue<TreeNode*> q;        q.push(root);        while (!q.empty()) {            int size = q.size();            for (int i = ; i < size; i++) {                TreeNode * temp = q.front();                q.pop();                if (temp->left) q.push(temp->left);                if (temp->right) q.push(temp->right);                if (i == size - ) {                    res.push_back(temp->val);                }            }        }        return res;    }};

9.Maximum Depth of Binary Tree（https://leetcode.com/problems/maximum-depth-of-binary-tree/description/）

递归解法：

class Solution {public:    int maxDepth(TreeNode* root) {        if (root == NULL) return ;        if (root->left == NULL && root->right == NULL) return ;        int maxl = maxDepth(root->left);        int maxr = maxDepth(root->right);        return maxl > maxr ? maxl +  : maxr + ;    }};

BFS解法：

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

10.Binary Tree Inorder Traversal(https://leetcode.com/problems/binary-tree-inorder-traversal/description/)

普通的中序遍历。

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

11.Validate Binary Search（https://leetcode.com/problems/validate-binary-search-tree/）

判断一棵二叉树是否二叉搜索树。

class Solution {public:    bool isValidBST(TreeNode* root) {        if (root == NULL) return true;        vector<int> seq;        inOrder(seq, root);        for (int i = ; i < seq.size() - ; i++) {            if (seq[i] >= seq[i + ]) return false;        }        return true;    }    void inOrder(vector<int> &seq, TreeNode *root) {        if (root == NULL) return;        else {            inOrder(seq, root->left);            seq.push_back(root->val);            inOrder(seq, root->right);        }    }};

12.Convert Sorted Array to Binary Search Tree（https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/）

使用分治法。

class Solution {public:    TreeNode* sortedArrayToBST(vector<int>& nums) {        return BSTNode(nums, , nums.size() - );    }    TreeNode* BSTNode(vector<int> &nums, int first, int last) {        if (first > last) return NULL;        else {            int mid = (first + last) / ;            TreeNode *root = new TreeNode(nums[mid]);            root->left = BSTNode(nums, first, mid - );            root->right = BSTNode(nums, mid + , last);            return root;        }    }};

13.Balanced Binary Tree（https://leetcode.com/problems/balanced-binary-tree/description/）

判断一棵二叉树是否平衡二叉树。

/** * 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 {public:    bool isBalanced(TreeNode* root) {        int depth = ;        return isBalanced(root, depth);    }    bool isBalanced(TreeNode* root, int &depth) {        if (root == NULL) {            depth = ;            return true;        }        else {            int LeftDepth;            int RightDepth;            bool isLeftBalanced = isBalanced(root->left, LeftDepth);            bool isRightBalanced = isBalanced(root->right, RightDepth);            if (isLeftBalanced && isRightBalanced) {                if (abs(LeftDepth - RightDepth) <= ) {                    depth = LeftDepth > RightDepth ? LeftDepth +  : RightDepth + ;                    return true;                }             }            return false;        }    }};