代码拉取完成,页面将自动刷新
同步操作将从 程序员大彬/Java-learning 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
Table of Contents generated with DocToc
二叉树的先序、中序和后序属于深度优先遍历DFS,层次遍历属于广度优先遍历BFS。
class Solution {
//方法1
public List<Integer> preorderTraversal1(TreeNode root) {
List<Integer> result = new ArrayList<>();
LinkedList<TreeNode> ll = new LinkedList<>(); //类型声明List改为LinkedList,List没有addFirst()/removeFirst()方法
while (root != null || !ll.isEmpty()) {
while (root != null) {
result.add(root.val);
ll.addFirst(root);
root = root.left;
}
root = ll.removeFirst();
root = root.right;
}
return result;
}
//方法2
public List<Integer> preorderTraversal2(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null) {
return result;
}
Stack<TreeNode> s = new Stack<>();
s.push(root);
while(!s.isEmpty()) {
TreeNode node = s.pop();
result.add(node.val);
if(node.right != null) {
s.push(node.right);//先压右,再压左
}
if(node.left != null) {
s.push(node.left);
}
}
return result;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> deque = new ArrayDeque<>();
while (!deque.isEmpty() || root != null) {
while (root != null) {
deque.push(root);
root = root.left;
}
root = deque.pop();
res.add(root.val);
root = root.right;
}
return res;
}
使用 null 作为标志位,访问到 null 说明此次递归调用结束。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
if (root != null) {
stack.push(root);//最后访问
stack.push(null);
if (root.right != null) {
stack.push(root.right);
}
if (root.left != null) {
stack.push(root.left);
}
} else { //值为null说明此次递归调用结束,将节点值存进结果
res.add(stack.pop().val);
}
}
return res;
}
}
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
LinkedList<TreeNode> queue = new LinkedList<>();
if (root == null) {
return res;
}
queue.addLast(root);
while (!queue.isEmpty()) {
List<Integer> levelList = new LinkedList<>();
int size = queue.size();
while (size-- > 0) {
root = queue.removeFirst();
levelList.add(root.val);
if (root.left != null) {
queue.addLast(root.left);
}
if (root.right != null) {
queue.addLast(root.right);
}
}
res.add(levelList);
}
return res;
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。