二十四期第十四天"/>
代码随想录算法训练营二十四期第十四天
递归前中后序遍历很简单!只需要注意当前节点的取出顺序就可以了。
迭代法的前中后序遍历较难,
题目链接:
前序遍历
递归遍历:
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;}
}
总结
二叉树的递归法遍历是比较简单的,而且速度很快。迭代法遍历比较难,而且速度较慢。
更多推荐
代码随想录算法训练营二十四期第十四天
发布评论