0101-0110

101. Symmetric Tree $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  bool isSymmetric(TreeNode* root) { return helper(root, root); }

 private:
  bool helper(TreeNode* p, TreeNode* q) {
    if (!p || !q) return p == q;

    return p->val == q->val &&
           helper(p->left, q->right) &&
           helper(p->right, q->left);
  }
};

102. Binary Tree Level Order Traversal $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};

    vector<vector<int>> ans;

    queue<TreeNode*> queue;
    queue.push(root);

    while (!queue.empty()) {
      vector<int> currLevel;
      for (int i = queue.size(); i > 0; --i) {
        TreeNode* node = queue.front();
        queue.pop();
        currLevel.push_back(node->val);
        if (node->left) queue.push(node->left);
        if (node->right) queue.push(node->right);
      }
      ans.push_back(currLevel);
    }

    return ans;
  }
};

103. Binary Tree Zigzag Level Order Traversal $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    if (!root) return {};

    vector<vector<int>> ans;
    deque<TreeNode*> deque;
    deque.push_back(root);
    bool isLeftToRight = true;

    while (!deque.empty()) {
      vector<int> currLevel;
      for (int i = deque.size(); i > 0; --i) {
        if (isLeftToRight) {
          TreeNode* node = deque.front();
          deque.pop_front();
          currLevel.push_back(node->val);
          if (node->left) deque.push_back(node->left);
          if (node->right) deque.push_back(node->right);
        } else {
          TreeNode* node = deque.back();
          deque.pop_back();
          currLevel.push_back(node->val);
          if (node->right) deque.push_front(node->right);
          if (node->left) deque.push_front(node->left);
        }
      }
      ans.push_back(currLevel);
      isLeftToRight = !isLeftToRight;
    }

    return ans;
  }
};

104. Maximum Depth of Binary Tree $\star$

1
2
3
4
5
6
7
8
class Solution {
 public:
  int maxDepth(TreeNode* root) {
    if (!root) return 0;

    return 1 + max(maxDepth(root->left), maxDepth(root->right));
  }
};

105. Construct Binary Tree from Preorder and Inorder Traversal $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> map;
    for (int i = 0; i < inorder.size(); ++i) map[inorder[i]] = i;

    return helper(preorder, 0, preorder.size() - 1, inorder, 0,
                  inorder.size() - 1, map);
  }

  TreeNode* helper(vector<int>& preorder, int pLeft, int pRight,
                   vector<int>& inorder, int iLeft, int iRight,
                   unordered_map<int, int>& map) {
    if (pLeft > pRight || iLeft > iRight) return nullptr;

    int i = map[preorder[pLeft]];
    TreeNode* curr = new TreeNode(preorder[pLeft]);
    curr->left = helper(preorder, pLeft + 1, pLeft + i - iLeft, inorder, iLeft,
                        i - 1, map);
    curr->right = helper(preorder, pLeft + i - iLeft + 1, pRight, inorder,
                         i + 1, iRight, map);

    return curr;
  }
};

106. Construct Binary Tree from Inorder and Postorder Traversal $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    unordered_map<int, int> map;
    for (int i = 0; i < inorder.size(); ++i) map[inorder[i]] = i;

    return helper(inorder, 0, inorder.size() - 1, postorder, 0,
                  postorder.size() - 1, map);
  }

  TreeNode* helper(vector<int>& inorder, int iLeft, int iRight,
                   vector<int>& postorder, int pLeft, int pRight,
                   unordered_map<int, int>& map) {
    if (iLeft > iRight || pLeft > pRight) return nullptr;

    int i = map[postorder[pRight]];
    TreeNode* curr = new TreeNode(postorder[pRight]);
    curr->left = helper(inorder, iLeft, i - 1, postorder, pLeft,
                        pLeft + i - iLeft - 1, map);
    curr->right = helper(inorder, i + 1, iRight, postorder, pLeft + i - iLeft,
                         pRight - 1, map);

    return curr;
  }
};

107. Binary Tree Level Order Traversal II $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  vector<vector<int>> levelOrderBottom(TreeNode* root) {
    if (!root) return {};

    vector<vector<int>> ans;

    queue<TreeNode*> queue;
    queue.push(root);

    while (!queue.empty()) {
      vector<int> currLevel;
      for (int i = queue.size(); i > 0; --i) {
        TreeNode* node = queue.front();
        queue.pop();
        currLevel.push_back(node->val);
        if (node->left) queue.push(node->left);
        if (node->right) queue.push(node->right);
      }
      ans.insert(ans.begin(), currLevel);
    }

    return ans;
  }
};

108. Convert Sorted Array to Binary Search Tree $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  TreeNode* sortedArrayToBST(vector<int>& nums) {
    return helper(nums, 0, nums.size() - 1);
  }

 private:
  TreeNode* helper(vector<int>& nums, int l, int r) {
    if (l > r) return NULL;

    int mid = (l + r) >> 1;
    TreeNode* root = new TreeNode(nums[mid]);

    root->left = helper(nums, l, mid - 1);
    root->right = helper(nums, mid + 1, r);

    return root;
  }
};

109. Convert Sorted List to Binary Search Tree $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  TreeNode* sortedListToBST(ListNode* head) {
    int length = 0;
    for (auto curr = head; curr; curr = curr->next) ++length;

    this->head = head;

    return helper(0, length - 1);
  }

 private:
  ListNode* head;

  TreeNode* helper(int l, int r) {
    if (l > r) return NULL;

    int mid = (l + r) >> 1;

    TreeNode* left = helper(l, mid - 1);
    TreeNode* node = new TreeNode(head->val);
    head = head->next;
    node->left = left;
    node->right = helper(mid + 1, r);

    return node;
  }
};

110. Balanced Binary Tree $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  bool isBalanced(TreeNode* root) {
    if (!root) return true;

    return abs(maxDepth(root->left) - maxDepth(root->right)) <= 1 &&
           isBalanced(root->left) && isBalanced(root->right);
  }

 private:
  int maxDepth(TreeNode* root) {
    if (!root) return 0;

    return 1 + max(maxDepth(root->left), maxDepth(root->right));
  }
};