leetcode算法题解整理之树专题部分_给定一棵具有 n 个节点的 特殊 二叉树的根节点 root 。特殊二叉树的节点编号从 1

leetcode算法题解整理之树专题部分

二叉树的结构体为：

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){}
};
1
2
3
4
5
6
7
8

98. 验证二叉搜索树

【题目描述】：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

【分析】：
INT_MIN < root->val < INT_MAX

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree

class Solution {
public:
	bool isValidBST(TreeNode* root) {
		return dfs(root, INT_MIN, INT_MAX);
	}
	bool dfs(TreeNode* root, long long minv, long long maxv) {
		if (!root) return true;
		if (root->val < minv || root->val >maxv) return false;
		return dfs(root->left, minv, root->val - 1ll) && dfs(root->right, root->val + 1ll, maxv);
	}
};
1
2
3
4
5
6
7
8
9
10
11

94. 二叉树的中序遍历

【题目描述】：给定一个二叉树的根节点 root ，返回它的 中序 遍历。
【分析】：
将整棵树的最左边一条链压入栈中，每次取出栈顶元素，如果它有右子树，则将右子树压入栈中。
【C++代码】：

class Solution {
public:
	vector<int>inorderTraversal(TreeNode* root) {
		vector<int> res;   
		stack<TreeNode*> stk;
		auto p = root;
		while (p || stk.size()) {
			while (p) {    //将整棵树的最左边一条链压入栈中
				stk.push(p);     
				p = p->left;
			}
			p = stk.top();
			stk.pop();              //取出栈顶元素
			res.push_back(p->val);  //放入容器中
			p = p->right;           //遍历右子树，压入栈中
		}
		return res;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

引入stack容器

概念：stack是一种先进后出的数据结构(First In Last Out),它只有一个出口

栈中只有栈顶元素才可以被外界使用，因此栈不允许有遍历行为
栈中进入数据称为 —入栈push
栈中弹出数据称为 —出栈pop

stack容器-常用接口

功能描述：栈容器常用的对外接口
构造函数：

stack<T> stk;        //stack采用模板类实现，stack对象的默认构造形式
stack(const stack&stk); //拷贝构造函数
1
2

赋值操作：

push(elem);     //向栈顶添加元素
pop();          //从栈顶移除第一个元素
top();          //返回栈顶元素
1
2
3

大小操作：

empty();       //判断栈是否为空
size();        //返回栈的大小
1
2

101. 对称二叉树

【题目描述】：给定一个二叉树，检查它是否是镜像对称的。
【分析】：
1、两个根节点的值要相等
2、左边的左子树和右边的右子树对称
3、左边的右子树和右边的左子树对此

递归方法：
【C++代码】：

class Solution {
public:
	bool isSymmetric(TreeNode* root) {
		if (!root) return true;
		return dfs(root->left, root->right);
	}
	bool dfs(TreeNode* p, TreeNode* q) {
		if (!p || !q) return !q && !p;
		//1、两个根节点的值要相等  p->val  == q->val
		//2、左边的左子树和右边的右子树对此dfs(p->left, q->right)
		//3、左边的右子树和右边的左子树对此dfs(p->right, q->left)
		return p->val == q->val && dfs(p->left, q->right) && dfs(p->right, q->left);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

迭代方法：
【分析】:
左边：左中右遍历
将整棵树的最左边一条链压入栈中，每次取出栈顶元素，如果它有右子树，则将右子树压入栈中。
右边：右中左遍历
将整棵树的最右边一条链压入栈中，每次取出栈顶元素，如果它有左子树，则将左子树压入栈中。
【C++代码】

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
      if(!root) return true;
      stack<TreeNode*>leftStk,rightStk;
      auto l = root->left,r = root->right;
      while(l||r||leftStk.size()||rightStk.size()){
          while(l&&r){
              leftStk.push(l),l = l->left;
              rightStk.push(r),r = r->right;
          }
          if(l||r) return false;
          l = leftStk.top(),leftStk.pop();
          r = rightStk.top(),rightStk.pop();
          if(l->val != r->val) return false;
          l = l->right, r = r->left;
      }
      return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

剑指 Offer 27. 二叉树的镜像

【题目描述】：请完成一个函数，输入一个二叉树，该函数输出它的镜像。
【分析】：

【C++代码】

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return nullptr;
        mirrorTree(root->left);
        mirrorTree(root->right);
        swap(root->left,root->right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10

105. 从前序与中序遍历序列构造二叉树

【题目描述】：根据一棵树的前序遍历与中序遍历构造二叉树。
【分析】： 前序遍历的第一个数字是root，前序遍历root->left的个数和中序遍历root->left个数相等。
【C++代码】:

class Solution {
public:
    unordered_map<int,int> pos;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for(int i = 0;i < n;i++){
         pos.insert(make_pair(inorder[i],i));
        }
        return dfs(preorder,inorder,0,n-1,0,n-1);
    }
    TreeNode* dfs(vector<int>&preorder,vector<int>&inorder,int pl,int pr,int il,int ir){
        if(pl > pr) return nullptr;
        int k = pos[preorder[pl]];
        int len = k-il;
        auto root = new TreeNode(preorder[pl]);
        root->left = dfs(preorder,inorder,pl+1,pl+len,il,k-1);
        root->right = dfs(preorder,inorder,pl+len+1,pr,k+1,ir);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

102. 二叉树的层序遍历

【题目描述】：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
【分析】：
【C++代码】:

class Solution {
public:
	vector<vector<int>> levelOrder(TreeNode* root) {
		vector<vector<int>> res;
		if (!root) return res;
		queue<TreeNode*>q;
		q.push(root);
		while (q.size()) {
			int len = q.size();
			vector<int> level;
			for (int i = 0; i < len; i++) {
				auto t = q.front();
				q.pop();
				level.push_back(t->val);
				if (t->left)q.push(t->left);
				if (t->right)q.push(t->right);
			}
			res.push_back(level);
		}
		return res;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

引入queue容器：

概念：queue是一种先进先出（First In First Out）的数据结果

队列容器允许从一端新增元素，从另一端移除元素
队列中只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为
队列中进数据称为 —入队push
队列中出数据称为 —出队pop

queue容器-常用的接口

功能描述：栈容器常用的对外接口
构造函数

queue<T> que;       //que采用模板类实现，queue对象的默认构造形式
queue(const queue &que);  //拷贝构造函数
1
2

赋值操作：

queue& operator=(cosnt queue&que);    //重载等号操作符
1

数据存取

push(elem);          //往队尾添加元素
pop();               //从队头移除第一个元素
back();              //返回最后一个元素
front();             //返回第一个元素
1
2
3
4

大小操作：

empty();           //判断堆栈是否为空
size();            //返回栈的大小
1
2

236. 二叉树的最近公共祖先

【题目描述】：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
【C++代码】:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //如果以root为根的子树中包含p和q,则返回它们的最近公共祖先
        //如果只包含p,则返回p
        //如果只包含q,则返回q
        //如果不包含，则返回nullptr
        if(!root||root==p||root ==q) return root;
        auto left = lowestCommonAncestor(root->left,p,q);
        auto right= lowestCommonAncestor(root->right,p,q);
        if(!left) return right;
        if(!right) return left;
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

543. 二叉树的直径

【题目描述】：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
【分析】： 枚举最高点，递归时需要计算，从当前节点往下走，深度的最大值
【C++代码】:

class Solution {
public:
	int ans = 0;
	int diameterOfBinaryTree(TreeNode* root) {
		dfs(root);
		return ans;
	}
	int dfs(TreeNode* root) {
		if (!root) return 0;
		int left = dfs(root->left);
		int right = dfs(root->right);
		ans = max(ans, left + right);
		return max(left + 1, right + 1);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

124. 二叉树中的最大路径和

【题目描述】：路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

【分析】： 枚举最高点

1. 向左走，-10 + L
2. 向右走，-10 + R
3. 不走， -10
   【C++代码】:

class Solution {
public:
    int ans = INT_MIN;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
    //返回从root向下走的最大值
    int dfs(TreeNode *root){
        if(!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        ans = max(ans,left+root->val + right);
        return max(0,root->val+max(left,right));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

173. 二叉搜索树迭代器

【题目描述】：实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。
【C++代码】:

class BSTIterator {
public:
    stack<TreeNode*> stk;
    BSTIterator(TreeNode* root) {
        while(root){
            stk.push(root);
            root = root->left;
        }
    }
    int next() {
        auto p = stk.top();
        stk.pop();
        int res = p->val;
        p = p->right;
        while(p){
            stk.push(p);
            p = p->left;
        }
        return res;
    }
    bool hasNext() {
        return !stk.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

297. 二叉树的序列化与反序列化

注意：一般情况下只有前序遍历，并不能唯一确定一棵二叉树
有前序遍历+中序遍历，就可以唯一确定一个二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        dfs1(root,res);
        return res;
    }
    inline void dfs1(TreeNode* root,string& res){
        if(!root){
            res +="#,";
            return ;
        }
        res +=to_string(root->val) +',';
        dfs1(root->left,res);
        dfs1(root->right,res);
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs2(data,u);
    }
    TreeNode* dfs2(string&data,int &u){
        if(data[u]=='#'){
            u +=2;
            return nullptr;
        }
        int t =0;
        bool is_minus = false;
        if(data[u] == '-'){
            is_minus = true;
            u++;
        }
        while(data[u] !=','){
            t = t*10 + data[u] -'0';
            u++;
        }
        u++;
        if(is_minus) t= -t;
        auto root = new TreeNode(t);
        root->left = dfs2(data,u);
        root->right = dfs2(data,u);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59