二叉树

1.二叉树的抽象类型

1
2
3
4
5
6
7
8
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };

一个二叉树结点包含值，左子树和右子树

2.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

每次访问一层，访问完一层后，从最左边的结点的左子树开始访问，所以先进先出

考虑用一个队列

先让根结点进来，然后我们取出根节点，先让根节点左子树进队列，然后再让右子树进队列，然后再取队头，此时又是根结点的左子树，保持了从左到右的顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void levelorder(TreeNode* root)
{
	queue<TreeNode*> q;
	q.push(root);
	while (!q.empty())
	{
		TreeNode* newroot = q.front();
		q.pop();
		cout << newroot->val;
		if (newroot->left)
		{
			q.push(newroot->left);
		}
		if (newroot->right)
		{
			q.push(newroot->right);
		}
	}
}

问题来了，怎么区分不同层呢

注意到每层遍历完最后一个元素后，此时队列中所有元素都是下一层的，那么队列的长度也就是元素的个数

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
vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> q;
	q.push(root);
    vector<vector<int>> b;
    if(!root)
    {
        return b;
    }
	while (!q.empty())
	{
        int size = q.size();
        vector<int> a;
        for(int i = 0;i<size;i++)
        {
            TreeNode* newroot = q.front();
            a.push_back(newroot->val);
            q.pop();
            if (newroot->left)
            {
                q.push(newroot->left);
            }
            if (newroot->right)
            {
                q.push(newroot->right);
            }
        }
        b.push_back(a);
	}
    return b;
    }

2.求二叉树的最小深度

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

思路很简单，直接前序遍历二叉树即可，先根，然后左，右

看左右子树是否为空，若为空，则就是第一个叶子结点

用一个p来从根节点出发，

然后前序遍历，每次length++,如果p=nullptr,那么就返回length

3.判断是否存在长度为targetSum的路径

逻辑很简单，递归

判断左子树是否有，有就true，

没有就看右子树，有就有，没有就没有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool hasPathSum(TreeNode* root, int targetSum) {
	if (!root)
	{
		return false;
	}
	if (!(root->left) && !(root->right))
	{
		targetSum -= root->val;
		return targetSum == 0 ? true : false;
	}
	int val = root->val;
	if (hasPathSum(root->left, targetSum - val))
	{
		return true;
	}
	else {
		return hasPathSum(root->right, targetSum - val);

	}
}

4.输出3的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        vector<int> path;
        helper(root, targetSum, path, result);
        return result;
    }
    
    void helper(TreeNode* node, int sum, vector<int>& path, vector<vector<int>>& result) {
        if (!node) return;
        
        path.push_back(node->val);
        
        if (!node->left && !node->right && sum == node->val) {
            result.push_back(path);
        }
        
        helper(node->left, sum - node->val, path, result);
        helper(node->right, sum - node->val, path, result);
        
        path.pop_back(); // backtrack
    }
};

注意：对于这种需要全局维护的变量，我们内部再用一个函数封装，就不会每次重置了