当前位置:   article > 正文

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

给定一棵具有 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/788855
推荐阅读
相关标签
  

闽ICP备14008679号