网站备案做网站必须,国外上市网络公司排名,做网站公司需要什么资质,京东网的公司全称是144/94/145. 二叉树的前、中、后序的递归遍历 以中序遍历为例#xff0c;其余类似#xff1a; 给定一个二叉树的根节点 root #xff0c;返回 它的 中序 遍历 。 代码示例#xff1a;
/*** Definition for a binary tree node.* struct TreeNode {* int val;* Tr…144/94/145. 二叉树的前、中、后序的递归遍历 以中序遍历为例其余类似 给定一个二叉树的根节点 root 返回 它的 中序 遍历 。 代码示例
/*** 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:void traversal(TreeNode* cur,vectorint vec){if(cur NULL) return;traversal(cur-left,vec);//左vec.push_back(cur-val);//中traversal(cur-right,vec);//右}vectorint inorderTraversal(TreeNode* root) {vectorint result;traversal(root,result);return result;}
}; 总结不同的遍历方式只需将前中后三行代码交换顺序即可 递归三要素 确定递归函数的参数和返回值 确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 确定终止条件 写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。 确定单层递归的逻辑 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。 144/94/145. 二叉树的前、中、后序的非递归遍历(迭代) 1. 前序遍历和后续遍历遍历节点和处理节点相同可共用一套规则 2. 中序遍历遍历节点和处理节点不相同 前序遍历
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint result;if (root NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node st.top(); // 中st.pop();result.push_back(node-val);if (node-right) st.push(node-right); // 右空节点不入栈if (node-left) st.push(node-left); // 左空节点不入栈}return result;}
};
后序遍历
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint result;if (root NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node st.top();st.pop();result.push_back(node-val);if (node-left) st.push(node-left); // 相对于前序遍历这更改一下入栈顺序 空节点不入栈if (node-right) st.push(node-right); // 空节点不入栈}reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了return result;}
}; 处理将元素放进result数组中访问遍历节点 中序遍历
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;TreeNode* cur root;while (cur ! NULL || !st.empty()) {if (cur ! NULL) { // 指针来访问节点访问到最底层st.push(cur); // 将访问的节点放进栈cur cur-left; // 左} else {cur st.top(); // 从栈里弹出的数据就是要处理的数据放进result数组里的数据st.pop();result.push_back(cur-val); // 中cur cur-right; // 右}}return result;}
};
102. 二叉树的层序遍历 给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 代码示例
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;vectorvectorint result;if(root ! NULL) que.push(root);while(!que.empty()){int size que.size();vectorint vec;while(size--){TreeNode* node que.front();que.pop();vec.push_back(node-val);if(node-left) que.push(node-left);if(node-right) que.push(node-right);}result.push_back(vec);}return result;}
};
107. 二叉树的层序遍历II 给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历 代码示例
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {queueTreeNode* que;vectorvectorint result;if(root ! NULL) que.push(root);while(!que.empty()){int size que.size();vectorint vec;while(size--){TreeNode* node que.front();que.pop();vec.push_back(node-val);if(node-left) que.push(node-left);if(node-right) que.push(node-right);} result.push_back(vec);}reverse(result.begin(),result.end());return result;}
}; 注意 以下写法是错的因为reverse 函数不返回任何值返回类型是 void它只是对输入范围内的元素进行原地修改。 return reverse(result.begin(),result.end()); 199. 二叉树的右视图 给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。 代码示例
class Solution {
public:vectorint rightSideView(TreeNode* root) {queueTreeNode* que;vectorint result;if(root ! NULL) que.push(root);while(!que.empty()){int size que.size();for(int i 0;isize;i){TreeNode* node que.front();que.pop();if(i (size - 1)) result.push_back(node-val);if(node-left) que.push(node-left);if(node-right) que.push(node-right);}} return result;}
};
226. 翻转二叉树 给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 代码示例
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root NULL) return root;swap(root-left, root-right); // 中invertTree(root-left); // 左invertTree(root-right); // 右return root;}
};
101. 对称二叉树 给你一个二叉树的根节点 root 检查它是否轴对称。 代码示例
class Solution {
public:bool compare(TreeNode* left, TreeNode* right) {// 首先排除空节点的情况if (left NULL right ! NULL) return false;else if (left ! NULL right NULL) return false;else if (left NULL right NULL) return true;// 排除了空节点再排除数值不相同的情况else if (left-val ! right-val) return false;// 此时就是左右节点都不为空且数值相同的情况// 此时才做递归做下一层的判断bool outside compare(left-left, right-right); // 左子树左、 右子树右bool inside compare(left-right, right-left); // 左子树右、 右子树左bool isSame outside inside; // 左子树中、 右子树中 逻辑处理return isSame;}bool isSymmetric(TreeNode* root) {if (root NULL) return true;return compare(root-left, root-right);}
};
104. 二叉树的最大深度 给定一个二叉树 root 返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 二叉树的 最大高度 是指最从远叶子节点到根节点的最长路径上的节点数。 代码示例
class Solution {
public:int getdepth(TreeNode* node) {if (node NULL) return 0;int leftdepth getdepth(node-left); // 左int rightdepth getdepth(node-right); // 右int depth 1 max(leftdepth, rightdepth); // 中return depth;}int maxDepth(TreeNode* root) {return getdepth(root);}
};
111. 二叉树的最小深度 给定一个二叉树找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明叶子节点是指没有子节点的节点。 代码示例
class Solution {
public:int getDepth(TreeNode* node) {if (node NULL) return 0;int leftDepth getDepth(node-left); // 左int rightDepth getDepth(node-right); // 右// 中// 当一个左子树为空右不为空这时并不是最低点if (node-left NULL node-right ! NULL) { return 1 rightDepth;} // 当一个右子树为空左不为空这时并不是最低点if (node-left ! NULL node-right NULL) { return 1 leftDepth;}int result 1 min(leftDepth, rightDepth);return result;}int minDepth(TreeNode* root) {return getDepth(root);}
};
222. 完全二叉树的节点个数 给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。 完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。 代码示例(普通二叉树解法)
class Solution {
private:int getNodesNum(TreeNode* cur) {if (cur NULL) return 0;int leftNum getNodesNum(cur-left); // 左int rightNum getNodesNum(cur-right); // 右int treeNum leftNum rightNum 1; // 中return treeNum;}
public:int countNodes(TreeNode* root) {return getNodesNum(root);}
};
完全二叉树解法
class Solution {
public:int countNodes(TreeNode* root) {if (root nullptr) return 0;TreeNode* left root-left;TreeNode* right root-right;int leftDepth 0, rightDepth 0; // 这里初始为0是有目的的为了下面求指数方便while (left) { // 求左子树深度left left-left;leftDepth;}while (right) { // 求右子树深度right right-right;rightDepth;}if (leftDepth rightDepth) {return (2 leftDepth) - 1; // 注意(21) 相当于2^2所以leftDepth初始为0}return countNodes(root-left) countNodes(root-right) 1;}
}; 参考如下 代码随想录
