德州商城网站建设,南宁网络技术,369网站建设,网站现在怎么做排名二叉树是一种重要的数据结构#xff0c;对二叉树的遍历也很重要。这里简单介绍三种二叉树中序遍历的方法。二叉树的中序遍历就是首先遍历左子树#xff0c;然后访问当前节点#xff0c;最后遍历右子树。对于下面的二叉树#xff0c;中序遍历结果如下#xff1a; 结果…
二叉树是一种重要的数据结构对二叉树的遍历也很重要。这里简单介绍三种二叉树中序遍历的方法。二叉树的中序遍历就是首先遍历左子树然后访问当前节点最后遍历右子树。对于下面的二叉树中序遍历结果如下 结果[5,10,6,15,2]
直观来看二叉树的中序遍历就是将节点投影到一条水平的坐标上。如图 1、递归法
这是思路最简单的方法容易想到并且容易实现。递归的终止条件是当前节点是否为空。首先递归调用遍历左子树然后访问当前节点最后递归调用右子树。代码如下 //recursive
class Solution1 {
public:vectorint inorderTraversal(TreeNode* root) {vectorint ret;if(rootNULL)return ret;inorderHelper(ret,root);return ret;}
private:void inorderHelper(vectorint ret,TreeNode* root){if(rootNULL)return;inorderHelper(ret,root-left);ret.push_back(root-val);inorderHelper(ret,root-right);}
};2、迭代法
在迭代方法中从根节点开始找二叉树的最左节点将走过的节点保存在一个栈中找到最左节点后访问对于每个节点来说它都是以自己为根的子树的根节点访问完之后就可以转到右儿子上了。代码如下
//iterate,using a stack
class Solution2 {
public:vectorint inorderTraversal(TreeNode* root) {vectorint ret;if(rootNULL)return ret;TreeNode *currroot;stackTreeNode* st;while(!st.empty()||curr!NULL){while(curr!NULL){st.push(curr);currcurr-left;}currst.top();st.pop();ret.push_back(curr-val);currcurr-right;}return ret;}
};这种方法时间复杂度是O(n)空间复杂度也是O(n)。 3、Morris法
这种方法是Morris发明的看完之后感觉精妙无比。这种方法不使用递归不使用栈O(1)的空间复杂度完成二叉树的遍历。这种方法的基本思路就是将所有右儿子为NULL的节点的右儿子指向后继节点对于右儿子不为空的节点右儿子就是接下来要访问的节点。这样对于任意一个节点当访问完它后它的右儿子已经指向了下一个该访问的节点。对于最右节点不需要进行这样的操作。注意这样的操作是在遍历的时候完成的完成访问节点后会把树还原。整个循环的判断条件为当前节点是否为空。例如上面的二叉树遍历过程如下根据当前节点c的位置
1当前节点为10因为左儿子非空不能访问找到c的左子树的最右节点p 结果[]
2找节点c的左子树的最右节点有两种终止条件一种右儿子为空一种右儿子指向当前节点。下面是右儿子为空的情况这种情况先要构造将节点p的右儿子指向后继节点c然后c下移 结果[]
3当前节点c的左儿子为空进行访问。访问后将c指向右儿子即后继节点 结果[5]
4继续寻找左子树的最右节点这次的终止条件是最右节点为当前节点。这说明当前节点的左子树遍历完毕访问当前节点后还原二叉树将当前节点指向后继节点 结果[5,10]
5重复上述过程直到c指向整棵二叉树的最右节点 左儿子为空进行访问c转到右儿子。右儿子为空不满足判断条件循环结束遍历完成。结果如下
[5,10,6,15,2]
这就是Morris方法时间复杂度为O(n)空间复杂度是O(1)。代码如下 //Morris traversal,without a stack
class Solution3 {
public:vectorint inorderTraversal(TreeNode* root) {vectorint ret;if(rootNULL)return ret;TreeNode *currroot;TreeNode *pre;while(curr){if(curr-leftNULL){ret.push_back(curr-val);currcurr-right;}else{precurr-left;while(pre-rightpre-right!curr)prepre-right;if(pre-rightNULL){pre-rightcurr;currcurr-left;}else{ret.push_back(curr-val);pre-rightNULL;currcurr-right;}}}return ret;}
};
