关联网站有那些,餐饮品牌网站建设,莆田网站建设费用,成都网站开发工作室上篇已经了解对二叉树有了大概了解#xff0c;本篇学习二叉树的前序、中序、后序及层序遍历的递归与非递归共7种遍历方法#xff0c;快收藏吧~
目录
1、前序遍历
递归方式#xff1a;
迭代方式#xff1a;
2、中序遍历
递归方式#xff1a; 迭代方式#xff1a;
…上篇已经了解对二叉树有了大概了解本篇学习二叉树的前序、中序、后序及层序遍历的递归与非递归共7种遍历方法快收藏吧~
目录
1、前序遍历
递归方式
迭代方式
2、中序遍历
递归方式 迭代方式
3、后序遍历
递归方式
迭代方式
4、层序遍历
递归方式
迭代方式 二叉树的前序、中序、后序及层序遍历的递归与非递归遍历方法
遍历(Traversal)是指沿着某条搜索路线依次对树中每个结 点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如打印节点内容、节点内容加 1)。 遍历是二叉树上最重要的操作之一是二叉树上进行其它运算之基础。 二叉树的遍历方法有以下四种 先序遍历根左右 首先访问根结点然后递归地遍历左子树最后遍历右子树。例如对于二叉树先序遍历的结果为1-2-4-8-9-5-10-11-3-6-7。 中序遍历左根右 首先遍历左子树然后访问根结点最后遍历右子树。例如对于二叉树中序遍历的结果为8-4-9-2-10-5-11-1-6-3-7。 后序遍历左右根 首先遍历左子树然后遍历右子树最后访问根结点。例如对于二叉树后序遍历的结果为8-9-4-10-11-5-2-6-7-3-1。 层序遍历 自上而下自左至右逐层访问树的结点的过程就是层序遍历。 它是按广度优先搜索的策略从根结点出发依次访问每一层上的节点。这种策略在实际应用中使用较多如在计算机图形学中用于渲染场景图等。例如对于二叉树层次遍历的结果为1-2-3-4-5-6-7-8-9-10-11 下面讲解代码前序遍历、中序遍历和后序遍历的简单递归方法不附图讲解主要解释它们的迭代方式及层序遍历 1、前序遍历
递归方式
定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义我们只要首先将 root 节点的值加入答案然后递归调用 preorder(root.left) 来遍历 root 节点的左子树最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可递归终止的条件为碰到空节点。
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();preorder(root, res);return res;}public void preorder(TreeNode root, ListInteger res) {if (root null) {return;}res.add(root.val);preorder(root.left, res);preorder(root.right, res);}
}
复杂度分析 时间复杂度O(n)其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。 空间复杂度O(n)为递归过程中栈的开销平均情况下为 O(logn)最坏情况下树呈现链状为 O(n)。 迭代方式
迭代的方式实现方法一的递归函数两种方式是等价的区别在于递归的时候隐式地维护了一个栈而我们在迭代的时候需要显式地将这个栈模拟出来其余的实现与细节都相同具体可以参考下面的代码。
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayList();if(rootnull) return res;StackTreeNode stack new Stack();stack.push(root);while(!stack.isEmpty()){TreeNode p stack.pop();res.add(p.val);if(p.right!null)stack.push(p.right);if(p.left!null)stack.push(p.left);}return res;}
}
注释 先将root压栈进入 while 循环每循环一次栈顶出栈一次并记录该结点将其左结点右结点压栈栈为空退出循坏。 时间复杂度O(n)其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。 空间复杂度O(n)为迭代过程中显式栈的开销平均情况下为 O(logn)最坏情况下树呈现链状为 O(n)。 2、中序遍历
递归方式
定义 inorder(root) 表示当前遍历到 root 节点的答案那么按照定义我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树然后将 root 节点的值加入答案再递归调用inorder(root.right) 来遍历 root 节点的右子树即可递归终止的条件为碰到空节点。
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();inorder(root, res);return res;}public void inorder(TreeNode root, ListInteger res) {if (root null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
}
复杂度分析 时间复杂度O(n)其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。 空间复杂度O(n)。空间复杂度取决于递归的栈深度而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别 迭代方式
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();StackTreeNode stack new Stack();while (root ! null || !stack.isEmpty()) {while (root ! null) {stack.push(root);root root.left;}root stack.pop();res.add(root.val);root root.right;}return res;}
}子循环中root遍历到root左子树最深层次过程中依次将左结点压栈左结点为空退出子循环将栈顶元素出栈 rootroot.right重新进入大循环既可遍历该树所有结点。 时间复杂度O(n)其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。 空间复杂度O(n)。空间复杂度取决于栈深度而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。 3、后序遍历
递归方式
定义 postorder(root) 表示当前遍历到 root 节点的答案。按照定义我们只要递归调用 postorder(root-left) 来遍历 root 节点的左子树然后递归调用 postorder(root-right) 来遍历 root 节点的右子树最后将 root 节点的值加入答案即可递归终止的条件为碰到空节点。
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();postorder(root, res);return res;}public void postorder(TreeNode root, ListInteger res) {if (root null) {return;}postorder(root.left, res);postorder(root.right, res);res.add(root.val);}
}复杂度分析 时间复杂度O(n)其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。 空间复杂度O(n)为递归过程中栈的开销平均情况下为 O(logn)最坏情况下树呈现链状为 O(n)。 迭代方式
我们也可以用迭代的方式实现方法一的递归函数两种方式是等价的区别在于递归的时候隐式地维护了一个栈而我们在迭代的时候需要显式地将这个栈模拟出来其余的实现与细节都相同具体可以参考下面的代码(为了更好的注释代码放入块引用中) class Solution { public ListInteger postorderTraversal(TreeNode root) { ListInteger res new ArrayListInteger(); if (root null) { return res; } Stack TreeNode stack new Stack(); TreeNode prev null; while (root ! null || !stack.isEmpty()) { while (root ! null) { stack.push(root); root root.left; } root stack.peek();// 取栈顶元素 //因为是后序遍历当前结点有无右结点决定它是否打印 //所以取出栈顶元素判断有无右结点 //而打印当前结点情况分为两种1、该结点无右结点 2、该结点的右结点已遍历 if (root.right null || root.right prev) { res.add(root.val); stack.pop(); prev root;//用prev指向root表示已被遍历 root null; } else root root.right; } return res; } } 如上图情况若if条件语句不判断 D.right ( K )是否被上次遍历则会陷入K出栈压栈无限循环中
复杂度分析 时间复杂度O(n)其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。 空间复杂度O(n)为迭代过程中显式栈的开销平均情况下为 O(logn)最坏情况下树呈现链状为 O(n)。 4、层序遍历
即逐层地从左到右访问所有节点。
递归方式
class Solution {ListListInteger resultnew ArrayList();public ListListInteger levelOrder(TreeNode root) {order(root,0);return result;}public void order(TreeNode node,int deep){if(nodenull)return;deep;if(result.size()deep){ListInteger itemnew ArrayList();result.add(item);}result.get(deep-1).add(node.val);order(node.left,deep);order(node.right,deep);}
}
在方法void order(TreeNode node,int deep) 传相应的结点和二维数组下标设置节点对应位置
加图理解 时间复杂度O(n) 迭代方式
代码设计重点出栈既遍历。在结点出栈时同时将不为空的左右结点入栈。进入子循环前用size记录栈内元素进入子循环后依次将栈顶元素弹出同时将不为空的左右结点入size--
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger resnew ArrayList();if(rootnull)return res;QueueTreeNode queuenew LinkedList();queue.offer(root);while(!queue.isEmpty()){int sizequeue.size();ListInteger listnew ArrayList();while(size--!0){TreeNode topqueue.poll();list.add(top.val);if(top.left!null)queue.offer(top.left);if(top.right!null)queue.offer(top.right);}res.add(list);}return res;}
} 时间复杂度O(n) 二叉树的遍历结束
