网站做视频在线观看,做网站是不是很简单,做苗木网站,wordpress the_excerpt()递归三要素#xff1a;
1.确定递归函数的参数和返回值#xff1a;确定哪些参数是递归的过程中需要处理的#xff0c;那么就在递归函数里加上这个参数#xff0c;并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2.确定终止条件#xff1a;写完了递归算…递归三要素
1.确定递归函数的参数和返回值确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2.确定终止条件写完了递归算法运行时经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。
3.确定单层递归的逻辑确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
以前序遍历为例
1.确定递归函数的参数和返回值因为要打印出前序遍历节点的数值所以参数里需要传入vector来放节点的数值除了这一点就不需要再处理什么数据也不需要有返回值所以递归函数返回类型就是void,代码如下
void traversal(TreeNode* cur,vectorint vec)
2.确定终止条件在递归的过程中如何算是递归结束了呢当然是当前遍历的节点是空了那么本层递归就要结束了所以如果当前遍历的这个节点是空就直接return,代码如下
if(cur NULL) return;
3.确定单层递归的逻辑前序遍历是中左右的循序所以单层递归的逻辑是要先取中节点的数值代码如下
vec.push_back(cur-val); //中
traversal(cur-left,wec); //左
traversal(cur-right,vec) //右
单层递归的1逻辑就是按照中左右的顺序来处理这样二叉树的前序遍历基本写完了再看一下完整代码
递归法
前序遍历
class Solution{
public:void traversal(TreeNode* cur,vectorintvec){if(cur NULL)return;vec.push_back(cur-val); //中traversal(cur-left,vec); //左traversal(cur-right,vec); //右}vectorintpreorderTraversal(TreeNode* root){vectorintresult;traversal(root,result);return result;}
};
中序遍历
void traversal(TreeNode* cur,vectorintvec){if(cur NULL)return;traversal(cur-left,vec); //左vec.push_back(cur-val); //中traversal(cur-right,vec); //右
}
后序遍历
void traversal(TreeNode* cur,vectorintvec){if(cur NULL)return;traversal(cur-left,vec);//左traversal(cur-right,vec);//右vec.push_back(cur-val);//中
}
迭代法
前序遍历迭代法
前序遍历是中左右每次先处理的是中间节点那么先将根节点放入栈中然后将右孩子加入栈再加入左孩子。
class Solution{
public:vectorintpreorderTraversal(TreeNode* root){stackTreeNode*st;vectorintresult;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;}
}
中序遍历迭代法不同于前序遍历不是改改就行。
首先迭代时有两个操作1.处理将元素放进result数组中 2.访问遍历节点
为什么遍历可以写一样的而迭代不行原因在于前序遍历的顺序是中左右先访问的元素是中间节点要处理的元素也是中间节点所以刚刚才能写出相对简洁的代码因为要访问的元素和要处理的元素顺序是一致的都是中间节点。
而中序遍历是左中右先访问的是二叉树顶部的节点然后一层一层向下访问直到到达树左面的最底部再开始处理节点也就是在把节点的数值放进result数组中这就造成了处理顺序和访问顺序是不一样的。
