二叉树遍历的非递归写法-创新互联
层次遍历,也就是我们常说的广度优先遍历
文章题目:二叉树遍历的非递归写法-创新互联
URL地址:http://scyanting.com/article/doehsj.html
这个相对来说比较简单,就是一层一层遍历,核心点是采用队列,queue
创新互联是一家专业提供隆昌企业网站建设,专注与成都网站制作、成都做网站、外贸营销网站建设、H5网站设计、小程序制作等业务。10年已为隆昌众多企业、政府机构等服务。创新互联专业网站建设公司优惠进行中。直接上代码
public static void levelTraversal(TreeNode root) {
if (root == null) {
return;
}
Queuequeue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode poll = queue.poll();
System.out.println(poll.value);
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
}
}
接下来是深度优先遍历,深度优先遍历分为三种,先序遍历,中序遍历,后续遍历而深度优先遍历,核心点是采用栈
先序遍历的非递归写法,大致有两种,一种是投机取巧,一种是标准写法直接上代码,投机取巧的写法
public static void preorderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stackstack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode pop = stack.pop();
System.out.println(pop.value);
if (pop.right != null) {
stack.push(pop.right);
}
if (pop.left != null) {
stack.push(pop.left);
}
}
}
标准写法
public static void preorderTraversal02(TreeNode root) {
if (root == null) {
return;
}
Stackstack = new Stack<>();
TreeNode temp = root;
while (temp != null || !stack.isEmpty()) {
while (temp != null) {
stack.push(temp);
System.out.println(temp.value);
temp = temp.left;
}
if (!stack.isEmpty()) {
TreeNode pop = stack.pop();
temp = pop.right;
}
}
}
然后是中序遍历,中序遍历没有投机取巧的方法,只有一种标准写法
public static void middleorderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stackstack = new Stack<>();
TreeNode temp = root;
while (temp != null || !stack.isEmpty()) {
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
if (!stack.isEmpty()) {
TreeNode pop = stack.pop();
System.out.println(pop.value);
temp = pop.right;
}
}
}
后序遍历,也有两种写法,一种投机取巧,一种标准写法
投机取巧的方式,代码如下
public static void postorderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stackstack = new Stack<>();
stack.push(root);
Listlist = new LinkedList<>();
while (!stack.isEmpty()) {
TreeNode pop = stack.pop();
list.add(pop);
if (pop.left != null) {
stack.push(pop.left);
}
if (pop.right != null) {
stack.push(pop.right);
}
}
Collections.reverse(list);
list.stream().forEach(System.out::println);
}
标准写法
public static void postorderTraversal02(TreeNode root) {
if (root == null) {
return;
}
Stackstack = new Stack<>();
TreeNode temp = root, lastNode = null;
while (temp != null || !stack.isEmpty()) {
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
// 查看当前栈顶元素
temp = stack.peek();
// 如果其右子树也为空,或者右子树已经访问过,则可以直接输出当前节点的值
if (temp.right == null || temp.right == lastNode) {
System.out.println(temp.value);
stack.pop();
// 把输出的节点赋值给lastNode游标,作为下次比对的依据
lastNode = temp;
temp = null;
} else {
// 否则,继续遍历右子树
temp = temp.right;
}
}
}
总结:
广度优先遍历比较简单,深度优先遍历,先序与中序标准写法是相同的代码结构,只需要一个指针,后续则不一样,需要记录上一次的遍历节点,需要两个指针,总的来说,练习一下都比较简单。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章题目:二叉树遍历的非递归写法-创新互联
URL地址:http://scyanting.com/article/doehsj.html