六六力扣刷题二叉树之迭代遍历

2023-12-13 38

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 六六力扣刷题二叉树之迭代遍历

前言

之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两天晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀

链表的合集

字符串

双指针

搜索二叉树

题目

迭代解法

前序迭代遍历

首先我们应该创建一个Stack用来存放节点，首先我们想要打印根节点的数据，此时Stack里面的内容为空，所以我们优先将头结点加入Stack，然后打印。

之后我们应该先打印左子树，然后右子树。所以先加入Stack的就是右子树，然后左子树。此时你能得到的流程如下:

其实思路是什么呢

第一我们先把节点放到栈里，然后只要栈不为空，我们就继续遍历，打印栈的左边
然后右边不存了，打印右边

public static void preOrderIteration(TreeNode head) {
  if (head == null) {
    return;
  }
  Stack<TreeNode> stack = new Stack<>();
  stack.push(head);
  while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    System.out.print(node.value + " ");
    if (node.right != null) {
      stack.push(node.right);
    }
    if (node.left != null) {
      stack.push(node.left);
    }
  }
}

比如上面的树，它的前序遍历的顺序是 1，2，4，8，9，5，3，6，7

中序遍历

public static void inOrderIteration(TreeNode head) {
  if (head == null) {
    return;
  }
  TreeNode cur = head;
  Stack<TreeNode> stack = new Stack<>();
  while (!stack.isEmpty() || cur != null) {
    while (cur != null) {
      stack.push(cur);
      cur = cur.left;
    }
    TreeNode node = stack.pop();
    System.out.print(node.value + " ");
    if (node.right != null) {
      cur = node.right;
    }
  }
}

后序遍历

public static void postOrderIteration(TreeNode head) {
    if (head == null) {
      return;
    }
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(head);
    while (!stack1.isEmpty()) {
      TreeNode node = stack1.pop();
      stack2.push(node);
      if (node.left != null) {
        stack1.push(node.left);
      }
      if (node.right != null) {
        stack1.push(node.right);
      }
    }
    while (!stack2.isEmpty()) {
      System.out.print(stack2.pop().value + " ");
    }
  }

总结

其实前中后的顺序遍历，其实代码差不多，差别就是在于顺序，然后就是前中后的顺序,不管是迭代法还是递归法，这都是最基础的，我们一定要会，大家记住，能用递归就能用迭代！我是小六六，三天打鱼，两天晒网！