00leetcode/20byTopic/12tree树.md · lionel/01BookNote

### 12.1、树的概念

```cpp
/**
 * 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) {}
 * };
 */
```

### 12.2、树的题目

#### 96、[不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees/)

```cpp
//转为一维动态规划了
int numTrees(int n) {
	vector<int> f(n+1,0);
	f[0]=1;
	f[1]=1;
	for(int i=2;i<=n;++i){
		for(int k=1;k<=i;++k)
			f[i]+=f[k-1]*f[i-k];
	}
	return f[n];
}
```

#### 98、[验证二叉搜索树]((https://leetcode.cn/problems/validate-binary-search-tree/))

```cpp
//[验证二叉搜索树 - 验证二叉搜索树 - 力扣（LeetCode）](https://leetcode.cn/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/)

//作者的思路没问题，主要在这个类型上，导致用例没有完全通过
bool isValidBST(TreeNode* root) {
	return isValidBST(root, LONG_MIN, LONG_MAX);
	//return isValidBST(root, INT_MIN, INT_MAX);
}

//bool isValidBST(TreeNode *root, int lower, int upper){
bool isValidBST(TreeNode *root, long long lower, long long upper){
	if(root==nullptr) return true;
	return root->val > lower && root->val < upper && isValidBST(root->left,lower,root->val) && isValidBST(root->right, root->val, upper);
}

//题解的答案
bool helper(TreeNode* root, long long lower, long long upper) {
    if (root == nullptr) {
        return true;
    }
    if (root -> val <= lower || root -> val >= upper) {
        return false;
    }
    return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
}
bool isValidBST(TreeNode* root) {
    return helper(root, LONG_MIN, LONG_MAX);
}
```

#### 102、[二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/)

```cpp
//递归
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    traverse(root,1,result);
    return result;
}

void traverse(TreeNode *root, size_t level, vector<vector<int>> &result){
    if(!root) return;
    if(level>result.size())
        result.push_back(vector<int>());
    result[level-1].push_back(root->val);
    traverse(root->left,level+1,result);
    traverse(root->right,level+1,result);
}
```

#### 104、二叉树的最大深度

```cpp
int maxDepth(TreeNode* root) {
    return root? 1 + max(maxDepth(root->left), maxDepth(root->right)): 0;
}
```

#### 105、[从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

```cpp
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	return buildTree(begin(preorder),end(preorder),begin(inorder),end(inorder));
}
template<typename InputIterator>
TreeNode* buildTree(InputIterator pre_first, InputIterator pre_last, InputIterator in_first, InputIterator in_last){
	if(pre_first == pre_last) return nullptr;
	if(in_first == in_last) return nullptr;
	auto root = new TreeNode(*pre_first);
	auto inRootPos = find(in_first, in_last, *pre_first);
	auto leftSize = distance(in_first, inRootPos);
	root->left = buildTree(next(pre_first),next(pre_first,leftSize+1),in_first,next(in_first,leftSize));
	root->right=buildTree(next(pre_first,leftSize+1),pre_last,next(inRootPos),in_last);
	return root;
}
```

#### 107、[二叉树的层序遍历II](https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/)

```cpp
//递归
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    traverse(root,1,result);
    std::reverse(result.begin(),result.end());//与102的差异在这一行
    return result;
}

#### 110、[是否为平衡树](https://leetcode.cn/problems/balanced-binary-tree/)

```cpp
// 主函数
bool isBalanced(TreeNode* root) {
return helper(root) != -1;
}
// 辅函数
int helper(TreeNode* root) {
if (!root) {
return 0;
}
int left = helper(root->left), right = helper(root->right);
    if (left == -1 || right == -1 || abs(left - right) > 1) {
return -1;
}
return 1 + max(left, right);
}

//另一个代码实现，思路应该是一样的
bool isBalanced(TreeNode* root) {
	return balancedHeight(root) >= 0;
}

//returns the height of root, if root is a balanced tree, otherwise, returns -1
int balancedHeight(TreeNode *root){
	if(root == nullptr) return 0; //终止
	int left = balancedHeight(root->left);
	int right = balancedHeight(root->right);
	if(left<0 || right<0 || abs(left-right)>1) return -1; //剪枝
	return max(left,right)+1;
}
```

#### 101、二叉树是否对称

```cpp
// 主函数
bool isSymmetric(TreeNode *root) {
return root? isSymmetric(root->left, root->right): true;
}
// 辅函数
bool isSymmetric(TreeNode* left, TreeNode* right) {
if (!left && !right) {
return true;
}
if (!left || !right) {
return false;
}
if (left->val != right->val) {
return false;
}
return isSymmetric(left->left, right->right) && isSymmetric(left->right,
right->left);
}
```

#### 111、

```cpp
//递归版
int minDepth(TreeNode* root) {
    return minDepth(root,false);
}

static int minDepth(TreeNode *root, bool hasbrother){
    if(!root) return hasbrother ?INT_MAX:0;
    return 1+min(minDepth(root->left, root->right != NULL),
    minDepth(root->right, root->left != NULL));
}

//迭代版
int minDepth(TreeNode* root) {
	if(root==nullptr) return 0;
	int result = INT_MAX;
	stack<pair<TreeNode*,int>> s;
	s.push(make_pair(root,1));

while(!s.empty()){
		auto node = s.top().first;
		auto depth = s.top().secnod;
		s.pop();
		if(node->left == nullptr && node->right == nullptr)
			result = min(result, depth);
		if(node->left && result > depth)  //深度控制，剪枝
			s.push(make_pair(node->left,depth+1));
		if(node->right && result > depth)  //深度控制，剪枝
			s.push(make_pair(node->right,depth+1));
	}
	return result;
}
```

#### 112、

```cpp
bool hasPathSum(TreeNode *root, int sum) {
    if(root == nullptr) return false;
    if(root->left==nullptr && root->right == nullptr) //leaf
        return sum = root->val;
    return hasPathSum(root->left, sum-root->val)
    || hasPathSum(root->right, sum-root->val);
}
```

#### 113、

```cpp
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    vector<vector<int>> result;
    vector<int> cur; //中间结果
    pathSum(root, targetSum, cur, result);
    return result;
}

void pathSum(TreeNode *root, int gap, vector<int> &cur, vector<vector<int>> &result){
    if(root == nullptr) return;
    cur.push_back(root->val);
    if(root->left == nullptr && root->right == nullptr) { //leaf
        if(gap == root->val)
            result.push_back(cur);
    }
    pathSum(root->left, gap-root->val,cur,result);
    pathSum(root->right, gap-root->val,cur,result);
    cur.pop_back();
}
```

#### 144、[二叉树的前序遍历]((https://leetcode.cn/problems/binary-tree-preorder-traversal/))

```cpp
void preorder(TreeNode* root, vector<int> &res){
if(root==NULL) return; 
res.push_back(root->val);
preorder(root->left,res); 
preorder(root->right,res); 
} 
vector<int> preorderTraversal(TreeNode* root) { 
vector<int> res; 
preorder(root, res);
return res; }
```

lionel/01BookNote

简介

发行版

贡献者

语言

近期动态

lionel/01BookNote .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

语言

近期动态

搜索帮助

lionel/01BookNote