二叉树的各种遍历姿势

本文主要是介绍二叉树的各种遍历姿势，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

Node节点

public static class TreeNode {TreeNode left;TreeNode right;int val;
}

定义

• 先序遍历：先访问根，再访问左子树，最后访问右子树
• 中序遍历：先访问左子树，再访问根，最后访问右子树
• 后序遍历：先访问左子树，再访问右子树，最后访问根

递归式模板

public void view(TreeNode root, List<Integer> result) {if(null == root) {return;}result.add(root.val);     // 根view(root.left, result);  // 左// result.add(root.val);view(root.right, result); // 右// result.add(root.val);
}

由根的访问时机可以得到不同的遍历顺序，根左右为先序，左根右为中序，左右根为后序

非递归式模板

先序、中序

public static List<Integer> preInOrder(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (null != cur || !stack.isEmpty()) {if (null != cur) {stack.push(cur);     // 入栈result.add(cur.val); // 访问（先序）cur = cur.left;      // 左行} else {cur = stack.pop();   // 出栈// result.add(cur.val); // 访问（中序）cur = cur.right;     // 右行}}return result;
}

入栈和左行之间访问节点，得到的是先序
出栈和右行之间访问节点，得到的是中序

后序

public static List<Integer> postOrder(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> tmp = new Stack<>();     // 辅助栈Stack<TreeNode> stack = new Stack<>();   // 主栈tmp.push(root);TreeNode cur = null;while (!tmp.isEmpty()) {// 从辅助栈取一个节点cur = tmp.pop();// 依次将其左右节点入辅助栈if (null != cur.left) {tmp.push(cur.left);}if (null != cur.right) {tmp.push(cur.right);}// 当前节点入主栈stack.push(cur);}while (!stack.isEmpty()) {result.add(stack.pop().val);}return result;
}

从辅助栈取出一个节点，依次将其左节点–>右节点压入辅助栈，再将本身压入主栈，循环至辅助栈空。
最后从主栈取出，根据栈性质易知得到的是左–>右–>根的顺序，即为后序。

层序

public static List<Integer> levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkList<TreeNode>();List<Integer> result = new ArrayList<>();if(null == root || null == root.val){return result;}queue.add(root);while(!queue.isEmpty()) {Integer e = queue.poll();result.add(root.val);// 左右节点入队列if(null != e.left) {queue.offer(e.left);}if(null != e.right) {queue.offer(e.right);}}return result;
}

这篇关于二叉树的各种遍历姿势的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---