发表于 | 更新于

题目

My way

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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:
    TreeNode* searchBST(TreeNode* root, int val) 
    {
        while (root)
        {
            if (root->val == val)   return root;
            if (root->val > val)    root = root->left;
            else    root = root->right;
        }

        return root;
    }
};

很简单的题目，就不写非递归实现了

发表于 | 更新于

题目

官方way

递归

java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        return containsOne(root) ? root : null;
    }

    public boolean containsOne(TreeNode node) {
        if (node == null) return false;
        boolean a1 = containsOne(node.left);
        boolean a2 = containsOne(node.right);
        if (!a1) node.left = null;
        if (!a2) node.right = null;
        return node.val == 1 || a1 || a2;
    }
}
C++实现
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
/**
 * 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 {
private:
    bool helper(TreeNode* root)
    {
        if (!root)  return false;

        bool lDel = helper(root->left);
        bool lRig = helper(root->right);

        if (!lDel)  root->left = nullptr;
        if (!lRig)  root->right = nullptr;

        return root->val == 1 | lDel | lRig;
    }

public:
    TreeNode* pruneTree(TreeNode* root) 
    {
        return helper(root) ? root : nullptr;
    }
};

总结

  • 自己一开始的递归思路不合理。
  • 递归终止条件： 到达nullptr处，return false
  • 递归状态：
    1. 当前结点值 == 1
    2. 左子树 == 全为1
    3. 右子树 == 全为1

Reference

https://leetcode-cn.com/problems/binary-tree-pruning/solution/er-cha-shu-jian-zhi-by-leetcode/

发表于 | 更新于

题目

My way

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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:
    TreeNode* invertTree(TreeNode* root) 
    {
        if (!root)  return nullptr;

        TreeNode* tmp = invertTree(root->right);
        root->right = invertTree(root->left);
        root->left = tmp;

        return root;        
    }
};

手动队列，层次遍历

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
/**
 * 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:
    TreeNode* invertTree(TreeNode* root) 
    {
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty())
        {
            auto front = q.front(); q.pop();
            if (!front) continue;

            auto tmp = front->right;
            front->right = front->left;
            front->left = tmp;

            q.push(front->left);
            q.push(front->right);
        }    

        return root;
    }
};

发表于 | 更新于

题目

递归实现

利用二叉搜索树的前序遍历结果中的左子树序列中的值都小于根节点。

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
/**
 * 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 {
private:
    TreeNode* helper(const vector<int>& nums, int l, int r)
    {
        if (l > r) return nullptr;
        TreeNode* root = new TreeNode(nums[l]);

        if (l == r) return root;
        int j = l + 1;
        
        while(nums[j] < nums[l])
        {
            ++j;
            if (j >= nums.size())   break;
        }

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

        return root;
    }
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) 
    {
        return helper(preorder, 0, preorder.size() - 1);   
    }
};
手动压栈实现
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* bstFromPreorder(vector<int>& preorder) {
       int n = preorder.size();
       if (!n)  return nullptr; 
       
       TreeNode* root = new TreeNode(preorder[0]);
       stack<TreeNode*> s;
       s.push(root);
       for (int i = 1; i < n; i++) 
       {
           TreeNode* node = s.top();
           TreeNode* child = new TreeNode(preorder[i]);
           while (!s.empty() && s.top()->val < child->val) 
           {
               node = s.top();
               s.pop();
           }
           if (node->val < child->val)     node->right = child;
           else                            node->left = child;
           s.push(child);
       }
       return root;
   }
};

References

NoNN way

https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/solution/jian-kong-er-cha-shu-by-leetcode/

发表于 | 更新于

题目

My way

记忆化搜索

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
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * 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 {
private:
unordered_map<int, vector<TreeNode*>> memo;

public:
    vector<TreeNode*> allPossibleFBT(int N) 
    {
        if (N % 2 == 0) return vector<TreeNode*>();

        //if (memo.count(N))    return memo[N];
        auto it = memo.find(N);
        if (it != memo.end())   return it->second;

        vector<TreeNode*> vt;

        if (N == 1)
        {
            vt.push_back(new TreeNode(0));
        } 
        else if (N % 2 == 1)
        {
            for (int x = 0; x < N; ++x)
            {
                int y = N - 1 - x;
                for (auto left: allPossibleFBT(x))
                {
                    for (auto right: allPossibleFBT(y))
                    {
                        TreeNode* bns = new TreeNode(0);
                        bns->left = left;
                        bns->right = right;
                        vt.push_back(bns);
                    }
                }
            }
        }
        memo.insert(make_pair(N, vt));
    
        return memo[N];
    }
};

发表于 | 更新于 | 分类于

题目

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (!t1)    return t2;
        if (!t2)    return t1;

        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);

        return t1;
    }
};

手动压栈实现

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
39
40
41
42
43
44
45
46
47
/**
 * 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:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (!t1)    return t2;
        if (!t2)    return t1;

        stack<pair<TreeNode*, TreeNode*>> s;
        s.push(make_pair(t1, t2));

        while (!s.empty())
        {
            auto root = s.top(); s.pop();

            if (!root.first|| !root.second)    continue;

            root.first->val += root.second->val;
            if (!root.first->left)
            {
                root.first->left = root.second->left;
            }
            else
            {
                s.push(make_pair(root.first->left, root.second->left));
            }

            if (!root.first->right)
            {
                root.first->right = root.second->right;
            }
            else
            {
                s.push(make_pair(root.first->right, root.second->right));
            }
        }

        return t1;
    }
};

总结

  • 可以用t1, t2的根节点来代替为新的根节点，实现起来会很方便。

    • 当你遍历到一个结点，其中只有一棵树有这样的结点的时候，递归实现直接返回另外一棵树的该节点即可。

Reference

https://leetcode-cn.com/problems/merge-two-binary-trees/solution/he-bing-er-cha-shu-by-leetcode/

发表于 | 分类于

题目

My way

递归解

要考虑3种情况：

  1. L，R分别在root的左，右子树上, \(val \in [L,\ R]\)
  2. L，R均在root的左子树上, \(L< R <val\)
  3. L，R均在root的右子树上, \(val > L > R\)
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
/**
 * 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 {
private:
    int sum = 0;
    void helper(TreeNode* root, int L, int R)
    {
        if (!root)  return ;

        if (L <= root->val && R >= root->val)
        {
            sum += root->val;
        }
        else if (L < root->val)
        {
            helper(root->right, L, R);
        }
        else if (R > root->val)
        {
            helper(root->left, L, R);
        }
    }

public:
    int rangeSumBST(TreeNode* root, int L, int R) 
    {
        helper(root, L, R);

        return sum;
    }
};

手动压栈

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
/**
 * 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:
    int rangeSumBST(TreeNode* root, int L, int R) 
    {
        int sum = 0;
        stack<TreeNode*> s;
        s.push(root);
        
        while (!s.empty())
        {
            root = s.top(); s.pop();
            if (!root)	continue;
            if (L <= root->val && root->val <= R)	sum += root->val;
            if (L < root->val)	s.push(root->left);
            if (R > root->val)	s.push(root->right);
		}

        return sum;    
    }
};

发表于 | 更新于 | 分类于

题目

没能理解题意。。。

我感觉是给了一个已经构造好的最大二叉树，然后新插入一个值为val的结点进来。

这个解答告诉了这个题是要做啥。然后发现是对比三幅例子的树图可以得到插入val结点进来的要求。

分成如下2种情况：

  1. 大于root，则把 root作为val节点的左子树；
  2. 小于root，则把 val节点作为root的右子树；

secretname way

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val)
    {
        if (!root || root->val < val)
        {
            TreeNode* node = new TreeNode(val);
            node->left = root;
            return node;
        }

        root->right = insertIntoMaxTree(root->right, val);
        return root;
    }
};

References

https://leetcode-cn.com/problems/maximum-binary-tree-ii/solution/go-0ms-wu-di-gui-by-yuhhen/

https://leetcode-cn.com/problems/maximum-binary-tree-ii/solution/c-di-gui-jian-ji-dai-ma-by-secretname/

发表于 | 分类于

题目

My way

递归构造树

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
/**
 * 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 {
private:
    TreeNode* helper(const vector<int>& nums)
    {
        auto it = max_element(nums.begin(), nums.end());
        if (it == nums.end())   return nullptr;
        TreeNode* root = new TreeNode(*it);
        root->left = helper(vector<int>(nums.begin(), it));
        root->right = helper(vector<int>(it + 1, nums.end()));

        return root;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* root = helper(nums);

        return root;    
    }
};

infinite way

单调栈

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
39
40
41
42
43
44
/**
 * 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:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        const int size = nums.size();
        vector<TreeNode*> st(size);
        int st_size = 0;
        for (const auto num : nums) {
            auto p = new TreeNode(num);
            if (st_size == 0 || st[0]->val < num) { // 栈内所有元素都比当前值小
                p->left = st[0];
                st[0] = p;
                st_size = 1;
            } else if (st[st_size - 1]->val > num) { // 栈内所有元素都比当前值大
                st[st_size - 1]->right = p;
                st[st_size++] = p;
            } else { // 二分查找临界位置
                int begin = 0;
                int end = st_size - 1;
                while (begin + 1 < end) {
                    auto half = (begin + end) / 2;
                    if (st[half]->val < num)
                        end = half;
                    else
                        begin = half;
                }
                p->left = st[end];
                st[begin]->right = p;
                st[begin + 1] = p;
                st_size = begin + 2;
            }
        }

        return st[0];
    }
};

修改了一下

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
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * 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:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        vector<TreeNode*> st(nums.size());

        int st_size = 0;
        for (const auto& num : nums)
        {
            auto p = new TreeNode(num);

            if (st_size == 0 || st[0]->val < num)   // 大于栈顶元素
            {
                p->left = st[0];
                st[0] = p;
                st_size = 1;
            }
            else if (st[st_size - 1]->val > num)	// 小于栈底元素 
            {
                st[st_size - 1]->right = p;
                st[st_size++] = p;
            }
            else	// 在栈中元素时，要找到这个元素的位置，然后设置它的left结点指向小于它的元素
            {
                int begin = 0, end = st_size - 1;
                while (begin + 1 < end)
                {
                    int half = (end - begin) / 2 + begin;
                   
                    if (st[half]->val < num)    end = half;
                    else                        begin = half;
                }

                p->left = st[end];
                st[begin]->right = p;
                st[begin + 1] = p;
                st_size = begin + 2;
            }
        }

        return st[0];
    }
};

总结

  • 这题刚好满足最大单调栈的应用场景，

    • 树结点的left, right的要求刚好对应单调栈里的左，右部分

Reference

https://leetcode-cn.com/problems/maximum-binary-tree/solution/c-dong-tai-gui-hua-by-infinite-15-7/