Leetcode_14 天数据结构入门_day12

Posted on | Edited on | In ,
| 3.6k | 30 mins.

树的题，有点意思啊。

226. Invert Binary Tree

Analysis

题意很简单，翻转二叉树。

Code

dfs

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        TreeNode *tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int size = q.size();
            for(int i = 0; i < size; i++) {
                TreeNode *tmp, *node = q.front(); q.pop();
                tmp = node->left;
                node->left = node->right;
                node->right = tmp;
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        return root;
    }
};

也可以写的更简单一点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode *tmp, *node = q.front(); q.pop();
            tmp = node->left;
            node->left = node->right;
            node->right = tmp;
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
        return root;
    }
};

112. Path Sum

Analysis

判断根节点到叶子结点的路径长度是否与给定值相等。

Code

dfs

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool dfs(TreeNode *root, int targetSum, int sum) {
        if(!root) return false;
        if(!root->left && !root->right && root->val + sum == targetSum) return true;
        return dfs(root->left, targetSum, sum + root->val) || dfs(root->right, targetSum, sum + root->val);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        return dfs(root, targetSum, 0);
    }
};

嗯，这样写，不够优雅，改一下：

1
2
3
4
5
6
7
8
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        if(!root->left && !root->right) return targetSum == root->val;
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

bfs

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
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        queue<TreeNode*> q;
        queue<int> sum;
        q.push(root);
        sum.push(root->val);
        while(!q.empty()) {
            TreeNode *node = q.front(); q.pop();
            int tmp = sum.front(); sum.pop();
            if(!node->left && !node->right) {
                if(tmp == targetSum) return true;
                continue;
            }
            if(node->left) {
                q.push(node->left);
                sum.push(node->left->val + tmp);
            }
            if(node->right) {
                q.push(node->right);
                sum.push(node->right->val + tmp);
            }
        }
        return false;
    }
};

使用 bfs 会麻烦一些，需要将所有根结点到叶子结点的路劲长度算出来，需要用队列来保存中间的计算结果，因为结点出队的顺序与根结点到这个结点的路劲长度是对应的。

Summary

树的题目有很多，有些题目很灵活，要多想想。不过本质都是一样的，那就是对树的遍历。

Buy me a coffee ? :)
0%