左神算法筆記: 5. 二叉樹的基本算法

二叉樹不能形成環

1. 先序、中序、後序周遊

   先序：對任意一個子樹的處理順序，都是先頭結點、再左子樹、再右子樹

   中序：左頭右

   後序：左右頭

   [image:710374ED-4483-43C6-8740-52B0AB1597BA-22873-00006BA364335C85/iShot2020-12-18 20.40.44.png]

2. 非遞歸方式實作二叉樹的先序、中序、後序
   1. 任何遞歸函數都可以改成非遞歸
   2. 自己設計壓棧的來實作
      • 先序實作邏輯：
        1. 放入head
        2. 循環（如果棧不為空）
           1. 出棧為head
           2. 列印head
           3. 如果有右，壓入右
           4. 如果有左，壓入左
      • 後序的實作邏輯：後序等于頭右左的倒叙 -> 準備兩個棧，head出棧的時候不直接列印，而是放入第二個棧
        1. 放入head
        2. 循環（stack1不為空）
           1. 如果有左，壓入s1
           2. 如果有右，壓入s1
        3. 循環（stack2不為空）
           1. 列印
      • 中序的實作邏輯：
        1. 整條左邊界依次入棧
        2. 彈出節點并列印，來到右樹執行邏輯1
      • 一個棧實作後序周遊（跳過）
3. 實作二叉樹的按層周遊
   1. 其實就是橫向優先搜尋，用 隊列
   2. 可以通過設定flag變量的方式， 來發現某一層的結束

public static void level(Node head) {
		if (head == null) {
			return;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			System.out.println(cur.value);
			if (cur.left != null) {
				queue.add(cur.left);
			}
			if (cur.right != null) {
				queue.add(cur.right);
			}
		}
	}
           

1. 統計二叉樹最寬的一行的寬度
   1. 方法一【使用map】：使用一個Map<Node, height> levelMap來記錄每個節點所對應的高度

public static int maxWidthUseMap(Node head) {
		if (head == null) {
			return 0;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		// key 在 哪一層，value
		HashMap<Node, Integer> levelMap = new HashMap<>();
		levelMap.put(head, 1);
		int curLevel = 1; // 目前你正在統計哪一層的寬度
		int curLevelNodes = 0; // 目前層curLevel層，寬度目前是多少
		int max = 0;
		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			int curNodeLevel = levelMap.get(cur);
			if (cur.left != null) {
				levelMap.put(cur.left, curNodeLevel + 1);
				queue.add(cur.left);
			}
			if (cur.right != null) {
				levelMap.put(cur.right, curNodeLevel + 1);
				queue.add(cur.right);
			}
			if (curNodeLevel == curLevel) {
				curLevelNodes++;
			} else {
				max = Math.max(max, curLevelNodes);
				curLevel++;
				curLevelNodes = 1;
			}
		}
		max = Math.max(max, curLevelNodes);
		return max;
	}
           

2. 方法二：其實并不在乎第幾層，隻在乎每行什麼時候結束
	- Node nextEnd用來在循環本層的時候記錄下一層的最右節點
	- Node curEnd用來記錄在本層的最右節點，當cur = curEnd的時候進行當層節點的結算，準備進入下一層
		1. max = Math.max(max, curLevelNodes)
		2. curLevelNodes = 0
		3. curEnd = nextEnd 指向下一個最後節點
           

public static int maxWidthNoMap(Node head) {
		if (head == null) {
			return 0;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		Node curEnd = head; // 目前層，最右節點是誰
		Node nextEnd = null; // 下一層，最右節點是誰
		int max = 0;
		int curLevelNodes = 0; // 目前層的節點數
		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			if (cur.left != null) {
				queue.add(cur.left);
				nextEnd = cur.left;
			}
			if (cur.right != null) {
				queue.add(cur.right);
				nextEnd = cur.right;
			}
			curLevelNodes++;
			if (cur == curEnd) {
				max = Math.max(max, curLevelNodes);
				curLevelNodes = 0;
				curEnd = nextEnd;
			}
		}
		return max;
	}
           

1. 二叉樹的序列化和反序列化【不要忽略Null節點】
   1. 可以用先序或者中序或者後序或者按層周遊，來實作二叉樹的序列化

   2. 用了什麼方式序列化，就用什麼方式反序列化

      序列化

      [image:4A49A2BC-1482-4ADC-B71D-461396CAF695-22873-00007B1F849017C5/iShot2020-12-19 10.19.36.png]

   • 先序：

public static void pres(Node head, Queue<String> ans) {
		if (head == null) {
			ans.add(null);
		} else {
			ans.add(String.valueOf(head.value));
			pres(head.left, ans);
			pres(head.right, ans);
		}
	}
           

- 按層
           

public static Queue<String> levelSerial(Node head) {
		Queue<String> ans = new LinkedList<>();
		if (head == null) {
			ans.add(null);
		} else {
			ans.add(String.valueOf(head.value));
			Queue<Node> queue = new LinkedList<Node>();
			queue.add(head);
			while (!queue.isEmpty()) {
				head = queue.poll(); // head 父   子
				if (head.left != null) {
					ans.add(String.valueOf(head.left.value));
					queue.add(head.left);
				} else {
					ans.add(null);
				}
				if (head.right != null) {
					ans.add(String.valueOf(head.right.value));
					queue.add(head.right);
				} else {
					ans.add(null);
				}
			}
		}
		return ans;
	}