[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 = 0; 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 = 1;
        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 == 0) {
                count = q.size();
                res.push_back(layer);
                layer.clear();
            }
        }
        for (int i = 0; i < res.size() / 2; i++) {
            vector<int> temp = res[i];
            res[i] = res[res.size() - i - 1];
            res[res.size() - i - 1] = 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 == 0 && 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, 0);
    } 
    int helper(TreeNode *root, int sum) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) return sum * 10 + root->val;
        else return helper(root->left, sum * 10 + root->val ) + helper(root->right, sum * 10 + 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 = 0; 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 - 1) {
                    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 0;
        if (root->left == NULL && root->right == NULL) return 1;
        int maxl = maxDepth(root->left);
        int maxr = maxDepth(root->right);
        return maxl > maxr ? maxl + 1 : maxr + 1;
    }
};

BFS解法：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int res = 0;
        if (root == NULL) return 0;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; 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 = 0; i < seq.size() - 1; i++) {
            if (seq[i] >= seq[i + 1]) 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, 0, nums.size() - 1);
    }
    TreeNode* BSTNode(vector<int> &nums, int first, int last) {
        if (first > last) return NULL;
        else {
            int mid = (first + last) / 2;
            TreeNode *root = new TreeNode(nums[mid]);
            root->left = BSTNode(nums, first, mid - 1);
            root->right = BSTNode(nums, mid + 1, 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 = 0;
        return isBalanced(root, depth);
    }
    bool isBalanced(TreeNode* root, int &depth) {
        if (root == NULL) {
            depth = 0;
            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) <= 1) {
                    depth = LeftDepth > RightDepth ? LeftDepth + 1 : RightDepth + 1;
                    return true;
                } 
                
            }
            return false;
        }
    }
};