import java.util.*;
/**
* @author : xfhy
* Create time : 2020年10月15日09:36:12
* Description : 144. 二叉树的前序遍历
* source : https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
*/
public class Solution {
public static 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;
}
}
//前序遍历: 即先遍历根节点,再遍历左右节点
//深度优先搜索(DFS) : 采用深度作为优先级,以便从根开始一直到达某个确定的叶子,然后再返回根到达另一个分支.深度优先搜索策略又可以根据根节点,左孩子和右孩子的相对顺序被细分为前序遍历,中序遍历,后续遍历
//宽度优先搜索(BFS) : 按照高度顺序一层一层的访问整棵树,高层次的节点将会比低层次的节点先被访问到
/**
* 递归思路: DFS 就是先遍历根节点,再遍历左右节点,easy~
*/
public static List<Integer> preorderTraversal(TreeNode root) {
List<Integer> preList = new LinkedList<>();
preHelper(root, preList);
return preList;
}
private static void preHelper(TreeNode root, List<Integer> preList) {
if (root == null) {
return;
}
preList.add(root.val);
preHelper(root.left, preList);
preHelper(root.right, preList);
}
/**
* 迭代思路: BFS
* 从根节点开始,每次迭代弹出栈顶节点,然后压入子节点,先压右节点,再压左节点. 每次弹出栈顶的时候将栈顶节点的数据存入结果List中.
* 最后的输出顺序是由上往下,由左往右 是符合前序遍历的顺序的
*/
public static List<Integer> preorderTraversal2(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> preList = new LinkedList<>();
if (root == null) {
return preList;
}
stack.add(root);
while (!stack.isEmpty()) {
TreeNode pop = stack.pop();
preList.add(pop.val);
if (pop.right != null) {
stack.push(pop.right);
}
if (pop.left != null) {
stack.push(pop.left);
}
}
return preList;
}
//------------------------------------扩展---------------------------------
/**
* 迭代算法 BFS 中序遍历(前中后)
* 从根节点开始找二叉树的最左节点,将走过的节点保存在一个栈中,找到最左节点后访问,对于每个节点来说,它都是以自己为根的子树的根节点,访问完之后就可以转到右儿子上了.
*/
public static List<Integer> middleOrderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> preList = new LinkedList<>();
if (root == null) {
return preList;
}
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
//找到最左边的节点,依次压入沿线所有节点
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
preList.add(curr.val);
curr = curr.right;
}
return preList;
}
public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
if (inputList == null || inputList.isEmpty()) {
return null;
}
TreeNode node = null;
Integer data = inputList.removeFirst();
if (data != null) {
node = new TreeNode(data);
node.left = createBinaryTree(inputList);
node.right = createBinaryTree(inputList);
}
return node;
}
public static void main(String[] args) {
/*LinkedList<Integer> integers = new LinkedList<>(Arrays.asList(5, 4, 11, 7, null, null, 2, null, null, null, 8, 13, null, null, 4,
5, null, null, 1));*/
/*LinkedList<Integer> integers = new LinkedList<>(Arrays.asList(3, 2, 9, null, null, 10, null,
null, 8, null, 4));*/
LinkedList<Integer> integers = new LinkedList<>(Arrays.asList(3, 9, null, null, 20, 15, null, null, 7));
TreeNode binaryTree = createBinaryTree(integers);
System.out.println(preorderTraversal(binaryTree));
}
}