LC94 Binary Tree Inorder Traversal

Problem

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

Think

中序遍历，两种方法：递归法和迭代法

Code
  • Approach 1
1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    helper(root, res);
    return res;
}
void helper(TreeNode* root, vector<int>& res){
    if(!root){
        return;
    }
    helper(root->left, res);
    res.push_back(root->val);
    helper(root->right, res);
}
  • Approach 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* p = root;
    while(!s.empty() || p){
        if(p){
            s.push(p);
            p = p->left;
        }
        else{
            TreeNode *t = s.top();
            s.pop();
            res.push_back(t->val);
            p = t->right;
        }
    }
    return res;
}

LC95 Unique Binary Search Trees II

Problem

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
Think

递归，选择所有可能的根节点i，然后将left ～ i - 1的部分用递归的方式构成左子树，将i + 1 ～ right的部分用递归的方式构成右子树，最后将所有可能的左右子树和根节点拼接起来，就可以得到所有可能的树的构成

Code 
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
vector<TreeNode*> generateTrees(int n) {
    if(n == 0){
        return {};
    }
    return helper(1, n);
}
vector<TreeNode*> helper(int left, int right){
    vector<TreeNode*> res;
    if(left > right){
        res.push_back(NULL);
        return res;
    }
    for(int i = left; i <= right; i++){
        vector<TreeNode*> lTree = helper(left, i - 1);
        vector<TreeNode*> rTree = helper(i + 1, right);
        for(auto l: lTree){
            for(auto r: rTree){
                TreeNode* tr = new TreeNode(i);
                tr->left = l;
                tr->right = r;
                res.push_back(tr);
            }
        }
    }
    return res;
}

LC96 Unique Binary Search Trees

Problem

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

1
2
3
4
5
6
7
8
9
10
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
Think

DP，对于长度i，取j为中心点，则dp[i] += dp[j - 1] * dp[i - j]，1 <= j <= i

Code 
1
2
3
4
5
6
7
8
9
10
11
int numTrees(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= i; j++){
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp.back();
}

LC98 Validate Binary Search Tree

Problem

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

1
2
3
4
5
6
    2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:

1
2
3
4
5
6
7
8
9
    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Think

递归，函数输入当前节点应该在的范围，如果节点不在这个范围内则返回false；然后递归判断左右子树即可

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
bool isValidBST(TreeNode* root) {
    return helper(root, NULL, NULL);
}
bool helper(TreeNode* root, TreeNode* lower, TreeNode* upper){
    if(!root) return true;
    if(lower && root->val <= lower->val) return false;
    if(upper && root->val >= upper->val) return false;

    if(!helper(root->left, lower, root)) return false;
    if(!helper(root->right, root, upper)) return false;

    return true;
}

LC99 Recover Binary Search Tree

Problem

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

  • A solution using O(n) space is pretty straight forward.
  • Could you devise a constant space solution?
Think

类似线索二叉树的方法，每次到子树的最右边的那个节点的时候就添加一个指针指向下一个应该遍历的节点

Code 
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
35
36
37
38
void swap(TreeNode* x, TreeNode* y){
    int tmp = x->val;
    x->val = y->val;
    y->val = tmp;
}
void recoverTree(TreeNode* root) {
    TreeNode *x = NULL, *y = NULL, *pred = NULL, *predecessor = NULL;
    while(root){
        if(root->left){
            predecessor = root->left;
            while(predecessor->right && predecessor->right != root){
                predecessor = predecessor->right;
            }
            if(!predecessor->right){
                predecessor->right = root;
                root = root->left;
            }
            else{
                if(pred && root->val < pred->val){
                    y = root;
                    if(x == NULL) x = pred;
                }
                pred = root;
                predecessor->right = NULL;
                root = root->right;
            }
        }
        else{
            if(pred && root->val < pred->val){
                y = root;
                if(x == NULL) x = pred;
            }
            pred = root;
            root = root->right;
        }
    }
    swap(x, y);
}

LC100 Same Tree

Problem

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

1
2
3
4
5
6
7
Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false
Think

递归判断左右子树即可

Code 
1
2
3
4
5
bool isSameTree(TreeNode* p, TreeNode* q) {
    if(!p && !q) return true;
    if(!p || !q) return false;
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right) && p->val == q->val;
}

LC102 Binary Tree Level Order Traversal

Problem

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]
Think

层序遍历，用队列即可

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<vector<int>> levelOrder(TreeNode* root) {
    if(!root) return {};
    queue<TreeNode*> s;
    s.push(root);
    vector<vector<int>> res;
    while(!s.empty()){
        int len = s.size();
        vector<int> cur;
        for(int i = 0; i < len; i++){
            TreeNode* node = s.front();
            cur.push_back(node->val);
            s.pop();
            if(node->left) s.push(node->left);
            if(node->right) s.push(node->right);
        }
        res.push_back(cur);
    }
    return res;
}

LC103 Binary Tree Zigzag Level Order Traversal

Problem

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
   3
  / \
9  20
   /  \
  15   7

return its zigzag level order traversal as:

1
2
3
4
5
[
    [3],
    [20,9],
    [15,7]
]
Think

层序遍历，用队列即可，然后加上一个flag表示这一层需不需要翻转

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    if(!root) return {};
    queue<TreeNode*> s;
    s.push(root);
    vector<vector<int>> res;
    int flag = 0;
    while(!s.empty()){
        int len = s.size();
        vector<int> cur;
        for(int i = 0; i < len; i++){
            TreeNode* node = s.front();
            cur.push_back(node->val);
            s.pop();
            if(node->left) s.push(node->left);
            if(node->right) s.push(node->right);
        }
        if(flag == 1){
            reverse(cur.begin(), cur.end());
        }
        flag = 1 - flag;
        res.push_back(cur);
    }
    return res;
}

Review

Tree最长用的方法主要有：

  • 递归，主要是根据树的结构特性，使得我们很容易找到和树的整体结构类似的子树（大多数时候就是左右子树）
  • 使用栈或者队列进行迭代，主要是利用BST的前序中序后续和层序遍历
  • 动态规划