二叉树的前序遍历、中序遍历和后序遍历

二叉树：

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 。

记住要点：

前序（根左右）、中序（左根右）、后序（左右根）
可以看到，说的前中后序其实指的是根在遍历时的位置

示例：

前序遍历：A–>B–>D–>F–>G–>H–>I–>E–>C

中序遍历：F->D–>H–>G–>I–>B–>E–>A–>C

后序遍历：F–>H–>I–>G–>D–>E–>B–>C–>A

Java编程实现：

144. 二叉树的前序遍历

难度：简单

题目描述：

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：

输入：root = [1,2]
输出：[1,2]
示例 5：

输入：root = [1,null,2]
输出：[1,2]

Java程序：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List preorderTraversal(TreeNode root) {List res = new ArrayList();preorder(root, res);return res;}public void preorder(TreeNode root, List res){if(root == null){return;}res.add(root.val);preorder(root.left, res);preorder(root.right, res);}
}

94. 二叉树的中序遍历

难度：简单

题目描述：

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：

输入：root = [1,2]
输出：[2,1]
示例 5：

输入：root = [1,null,2]
输出：[1,2]

Java程序：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List inorderTraversal(TreeNode root) {List res = new ArrayList();inorder(root, res);return res;}public void inorder(TreeNode root, List res){if(root == null){return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
}

145. 二叉树的后序遍历

难度：简单

题目描述：

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

Java程序：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List postorderTraversal(TreeNode root) {List res = new ArrayList ();postorder(root, res);return res;}public void postorder(TreeNode root, List res){if(root == null){return;}postorder(root.left, res);postorder(root.right, res);res.add(root.val);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！