一、简介
二叉树有先序、中序和后序三种遍历方式。 关注根的位置，便于理解先中后。
1️⃣先序遍历【根左右】
- 访问根节点；
- 采用先序递归遍历左子树；
- 采用先序递归遍历右子树。
注：每个节点的分支都遵循上述的访问顺序，体现”递归调用”
2️⃣中序遍历【左根右】
- 采用中序遍历左子树；
- 访问根节点；
- 采用中序遍历右子树。
3️⃣后序遍历：【左右根】
- 采用后序递归遍历左子树；
- 采用后序递归遍历右子树；
- 访问根节点。
public class TreeNode {
public TreeNode left;
public TreeNode right;
public Integer val;
public TreeNode(int val) {
this.val = val;
}
}
二、先序遍历
public class PreorderTraversal {
public List<Integer> preorder(TreeNode root){
ArrayList<Integer> res = new ArrayList<>();
accessTree(root,res);
return res;
}
private void accessTree(TreeNode root, ArrayList<Integer> res) {
if(root==null){
return;
}
res.add(root.val);
accessTree(root.left,res);
accessTree(root.right,res);
}
public List<Integer> preorder02(TreeNode root){
ArrayList<Integer> res = new ArrayList<>();
Deque<TreeNode> stack=new LinkedList<>();
while(root!=null||!stack.isEmpty()){
while(root!=null){
res.add(root.val);
stack.push(root);
root=root.left;
}
root=stack.pop();
root=root.right;
}
return res;
}
}
三、中序遍历
public class InorderTraversal {
public List<Integer> inOrder(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
accessTree(root, res);
return res;
}
private void accessTree(TreeNode root, ArrayList<Integer> res) {
if (root == null) {
return;
}
accessTree(root.left, res);
res.add(root.val);
accessTree(root.right, res);
}
public List<Integer> inOrder02(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
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;
}
}
四、后序遍历
public class PostorderTraversal {
public List<Integer> postorder(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
accessTree(root, res);
return res;
}
private void accessTree(TreeNode root, ArrayList<Integer> res) {
if (root == null) {
return;
}
accessTree(root.left, res);
accessTree(root.right, res);
res.add(root.val);
}
public List<Integer> postorder02(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode preAccess = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == preAccess) {
res.add(root.val);
preAccess = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return res;
}
}
五、测试
public static void main(String[] args) {
TreeNode root = new TreeNode(0);
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
PreorderTraversal preorder = new PreorderTraversal();
List<Integer> preorderRes = preorder.preorder(root);
System.out.println(Arrays.toString(preorderRes.toArray()));
InorderTraversal inorder = new InorderTraversal();
List<Integer> inorderRes = inorder.inOrder(root);
System.out.println(Arrays.toString(inorderRes.toArray()));
PostorderTraversal postorder = new PostorderTraversal();
List<Integer> postorderRes = postorder.postorder(root);
System.out.println(Arrays.toString(postorderRes.toArray()));
}
Original: https://blog.csdn.net/ChineseSoftware/article/details/127820079
Author: hfnjfudnnr
Title: 二叉树的先序、中序和后序遍历
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/657165/
转载文章受原作者版权保护。转载请注明原作者出处！