六六力扣刷題二叉樹之疊代周遊

前言

之前小六六一直覺得自己的算法比較菜，算是一個短闆吧，以前刷題也還真是三天打魚，兩天曬網，刷幾天，然後就慢慢的不堅持了，是以這次，借助平台的活動，打算慢慢的開始開刷，并且自己還會給刷的題總結下，談談自己的一些思考，和自己的思路等等，希望對小夥伴能有所幫助吧，也可以借此機會把自己短闆補一補，希望自己能堅持下去呀

連結清單的合集

• ​​六六力扣刷題哈希表之哈希理論​​
• ​​六六力扣刷題哈希表之有效的字母異位詞​​
• ​​六六力扣刷題哈希表之兩個數組的交集​​
• ​​六六力扣刷題哈希表之快樂數​​
• ​​六六力扣刷題哈希表之贖金信​​
• ​​六六力扣刷題哈希表之三數之和​​

字元串

• ​​六六力扣刷題字元串之反轉字元串​​
• ​​六六力扣刷題字元串之反轉字元串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);
    }
  }
}      

中序周遊

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 + " ");
    }
  }      

總結