代码随想录算法训练营二十四期第十四天

二十四期第十四天"/>

代码随想录算法训练营二十四期第十四天

递归前中后序遍历很简单！只需要注意当前节点的取出顺序就可以了。
迭代法的前中后序遍历较难，
题目链接：

前序遍历

递归遍历：

class Solution {public void preTravel(List<Integer>list,TreeNode root) {if(root == null) return;list.add(root.val);preTravel(list, root.left);preTravel(list, root.right);}public List<Integer> preorderTraversal(TreeNode root) {List<Integer>list = new ArrayList<>();preTravel(list, root);return list;}
}

迭代遍历：（利用栈来实现）

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer>list = new ArrayList<>();Stack<TreeNode>stack = new Stack<>();if(root == null) return list;stack.push(root);while(!stack.empty()) {TreeNode node = stack.peek();if(node != null) {stack.pop();//现将中间节点弹出if(node.right != null) stack.push(node.right);//如果右右子节点，将右子节点插入栈中if(node.left != null) stack.push(node.left);//如果有左子结点，将左子结点插入栈中stack.push(node);//插入中间节点stack.push(null);//中间结点访问过，但是还没处理，添加一个空节点对其进行标记}else {stack.pop();//将空节点删除node = stack.peek();stack.pop();//取出栈顶元素list.add(node.val);//放到结果集}}return list;}
}

中序遍历

递归遍历：

class Solution {public void inTravel(List<Integer>list, TreeNode root) {if(root == null) return;inTravel(list, root.left);list.add(root.val);inTravel(list,root.right);}public List<Integer> inorderTraversal(TreeNode root) {List<Integer>list = new ArrayList<>();inTravel(list, root);return list;}
}

迭代遍历：

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer>list = new ArrayList<>();Stack<TreeNode>stack = new Stack<>();if(root == null) return list;stack.push(root);while(!stack.isEmpty()) {TreeNode node = stack.peek();if(node != null) {stack.pop();if(node.right != null) stack.push(node.right);//添加右节点，空节点不入栈stack.push(node);//添加中间节点stack.push(null); //中间结点访问过但还没处理，添加空节点做标记if(node.left != null) stack.push(node.left);//添加左节点，空节点不入栈}else {stack.pop();//将空节点弹出node = stack.pop();//取出栈中元素list.add(node.val);//放入结果集}}return list;}

后序遍历

递归遍历：

class Solution {public void postTravel(List<Integer>list,TreeNode root) {if(root == null) return;postTravel(list, root.left);postTravel(list, root.right);list.add(root.val);}public List<Integer> postorderTraversal(TreeNode root) {List<Integer>list = new ArrayList<>();postTravel(list, root);return list;}
}

迭代遍历：

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer>list = new ArrayList<>();Stack<TreeNode>stack = new Stack<>();if(root == null) return list;stack.push(root);while(!stack.isEmpty()) {TreeNode node = stack.peek();if(node != null) {stack.push(null);//访问过中间结点，但还没处理，添加空节点，对中间节点做标记if(node.right != null) stack.push(node.right);//添加右子节点if(node.left != null) stack.push(node.left);//添加左子结点}else {stack.pop();node = stack.pop();list.add(node.val);}}return list;}
}

总结

二叉树的递归法遍历是比较简单的，而且速度很快。迭代法遍历比较难，而且速度较慢。