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

时间：2022-10-30 18:00:29


前言

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

链表的合集

  • ​​六六力扣刷题哈希表之哈希理论​​
  • ​​六六力扣刷题哈希表之有效的字母异位词​​
  • ​​六六力扣刷题哈希表之两个数组的交集​​
  • ​​六六力扣刷题哈希表之快乐数​​
  • ​​六六力扣刷题哈希表之赎金信​​
  • ​​六六力扣刷题哈希表之三数之和​​

字符串

  • ​​六六力扣刷题字符串之反转字符串​​
  • ​​六六力扣刷题字符串之反转字符串2​​
  • ​​六六力扣刷题字符串之替换空格​​
  • ​​六六力扣刷题字符串之反转字符串中的单词​​
  • ​​六六力扣刷题字符串之找出字符串中第一个匹配项的下​​
  • ​​六六力扣刷题字符串之重复的子字符串​​

双指针

  • ​​六六力扣刷题双指针之移除元素​​
  • ​​六六力扣刷题双指针之删除链表的倒数第N个节点​​
  • ​​六六力扣刷题双指针之链表相交​​
  • ​​六六力扣刷题双指针之三数之和​​
  • ​​六六力扣刷题双指针之反转链表​​

搜索二叉树

  • ​​六六力扣刷题二叉树之基础​​
  • ​​六六力扣刷题二叉树之递归遍历​​

题目

迭代解法

前序迭代遍历

首先我们应该创建一个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 + " ");
    }
  }

总结

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

标签：

相关文章