Leetcode算法题

二叉树的中序遍历

给定一个二叉树的根节点root，返回它的中序遍历。

中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。

因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

class Solution{
public:
	void inorder(TreeNode *root, vector<int>& res){
		if(!root){
			return;
		}
		inorder(root->left, res);
		res.push_back(root->val);
		inorder(root->right, res);
	}
	vector<int> inorderTraversal(TreeNode* root){
		vector<int> res;
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

相同的树

给两棵二叉树的根节点p和q，编写一个函数验证这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

找出数组中的K-or值

给一个下标从0开始的整数数组nums和一个整数k。
nums中的K-or是一个满足以下条件的非负整数：

• 只有在nums中，至少存在k个元素的第i位值为1，那么K-or中的第i位的值才是1。

对称二叉树递归

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

因此，该问题可以转化为：两个树在什么情况下互为镜像？
如果同时满足下面的条件，两个树互为镜像：

• 它们的两个根节点具有相同的值
• 每个树的右子树都与另一个树的左子树镜像对称

我们可以实现这样一个递归函数，通过同步移动两个指针的方法来遍历这棵树，p指针和q指针一开始都指向这棵树的根，随后p右移时，q左移，p左移时，q右移。每次检查当前p和q节点的值是否相等，如果相等再判断左右子树是否对称。

class Solution{
public:
	bool check(TreeNode *p,TreeNode *q){
		if(!p && !q)
			return true;
		if(!p || !q)
			return false;
		return (p->val == q->val) && check(p->left,q->right) && check(p->right,q->left);
	}
	bool isSymmetric(TreeNode *root){
		return check(root,root);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

二叉树的最大深度

给定一个二叉树root，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点树。

深度优先搜索

如果我们知道了左子树和右子树的最大深度为l和r，那么该二叉树的最大深度为：
max(l,r)+1

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root){
            return 0;
        }
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return (left>right? left:right)+1;
    }
};
1
2
3
4
5
6
7
8
9
10
11

将有序数组转换为二叉搜索树

给定一个整数数组nums，其中元素已经按升序排列，请将其转换为一颗高度平衡二叉搜索树。

高度平衡二叉树是一颗满足每个节点的左右两个子树的高度差的绝对值不超过1的二叉树。

二叉搜索树的中序遍历是升序序列，题目给定的数组是按照升序排序的有序数组，因此可以确保数组是二叉搜索树的中序遍历序列。

给定二叉搜索树的中序遍历，是否可以唯一地确定二叉搜索树？
如果没有要求二叉搜索树的高度平衡，则任何一个数字都可以作为二叉搜索树的根节点，因此可能的二叉搜索树有多个。

如果增加一个限制条件，即要求二叉搜索树的高度平衡，是否可以唯一地确定二叉搜索树？答案仍然是否定的。

直观地看，可以选择中间数字作为二叉搜索树的根节点，这样分给左右子树的数字个数相同或只相差1，可以使得树保持平衡。

如果数组长度是奇数，则根节点的选择是唯一的，如果数组长度是偶数，则可以选择中间位置左边的数字作为根节点或选择中间位置右边的数字作为根节点，选择不同数字作为根节点，创建的平衡二叉树也是不同的。

确定平衡二叉搜索树的根节点之后，其余的数字分别位于平衡二叉搜索树的左子树和右子树中，左子树和右子树分别也是平衡二叉搜索树。

中序遍历，总是选择中间位置左边的数字作为根节点

选择中间位置左边的数字作为根节点，则根节点的下标为mid = (left+right)/2

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size()-1);
    }
    TreeNode* helper(vector<int>& nums, int left, int right){
        if(left > right){
            return nullptr;
        }

        //总是选择中间位置左边的数字作为根节点
        int mid = (left + right)/2;
        TreeNode *root = new TreeNode(nums[mid]);
        root->left = helper(nums,left,mid-1);
        root->right = helper(nums,mid+1,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

平衡二叉树

求长度版本

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int treeLength(TreeNode* root){
        if(!root){
            return 0;
        }
        int left = treeLength(root->left);
        int right = treeLength(root->right);
        return (left>right ? left:right)+1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root)
            return true;
        if(abs(treeLength(root->left)-treeLength(root->right))>1){
            return false;
        }
        return isBalanced(root->left) && isBalanced(root->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

二叉树的最小深度

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

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

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root){
            return 0;
        }else if(!root->left && !root->right){
            return 1;
        }else if(!root->left){
            return minDepth(root->right)+1;
        }else if(!root->right){
            return minDepth(root->left)+1;
        }else{
            return min(minDepth(root->right),minDepth(root->left))+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
26
27

注意：一定要子树都没有才算叶子结点