前言
学妹竟直呼内行！
二叉树层序遍历
使用广度优先搜索（BFS）
public class Main {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null)
return res;
Deque<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
while (size-- > 0) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(list);
}
return res;
}
}
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;
}
}
递归法
二叉树前序遍历
public class Main {
List<Integer> res;
public List<Integer> preorderTraversal(TreeNode root) {
res = new ArrayList<>();
if(root == null)
return res;
preTreeNode(root);
return res;
}
private void preTreeNode(TreeNode root) {
if(root == null) return;
res.add(root.val);
preTreeNode(root.left);
preTreeNode(root.right);
}
}
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;
}
}
复杂度分析
-
时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
-
空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。
二叉树中序遍历
public class Main {
List<Integer> res;
public List<Integer> inorderTraversal(TreeNode root) {
res = new ArrayList<>();
if (root == null)
return res;
midTreeNode(root);
return res;
}
private void midTreeNode(TreeNode root) {
if (root == null) return;
midTreeNode(root.left);
res.add(root.val);
midTreeNode(root.right);
}
}
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;
}
}
二叉树后序遍历
public class Main {
List<Integer> res;
public List<Integer> postorderTraversal(TreeNode root) {
res = new ArrayList<>();
if(root == null)
return res;
postTreeNode(root);
return res;
}
private void postTreeNode(TreeNode root) {
if(root == null) return;
postTreeNode(root.left);
postTreeNode(root.right);
res.add(root.val);
}
}
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;
}
}
迭代法
二叉树前序遍历
与递归方法相差无几，只是把递归中隐藏的栈显示出来
因为栈的特性，我们需要先把右子节点push到栈中，再push左子节点，这样拿出来的时候就是先拿出左子节点。
public class Main {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return res;
}
}
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;
}
}
二叉树中序遍历
中序遍历式按 左 中 右的顺序输出节点。
所以我们尽可能的把节点的左子树压入栈中，这样栈顶元素为最左侧节点
在pop出来后，将其右子节点push进去，这样的话就是按照中序遍历获取元素啦
public class Main {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
while(cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
res.add(node.val);
if(node.right != null) {
cur = node.right;
}
}
return res;
}
}
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;
}
}
二叉树后序遍历
- 首先将根节点压栈
- 因为先出栈的为根节点，其后先出右子节点，最后出左子节点
- 将左子节点压栈
- 将右子节点压栈
- 因为出栈顺序为“根右左”，所以需要每次将元素插入list开头
public class Main {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if (root == null)
return result;
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left != null)
stack.push(node.left);
if (node.right != null) {
stack.push(node.right);
}
result.add(0, node.val);
}
return result;
}
}
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;
}
}
最后
我是 Code皮皮虾，一个热爱分享知识的 皮皮虾爱好者，未来的日子里会不断更新出对大家有益的博文，期待大家的关注！！！
创作不易，如果这篇博文对各位有帮助，希望各位小伙伴可以点赞和关注我哦，感谢支持，我们下次再见~~~
分享大纲
更多精彩内容分享，请点击 Hello World (●’◡’●)
转载：https://blog.csdn.net/llllllkkkkkooooo/article/details/117023217
查看评论