#226. Invert Binary Tree

題目描述

給你一個二元樹，反轉它，並且回傳。

限制條件

1. 二元樹節點數量介於[0, 100]。
2. -100 <= 節點值 <= 100

解題思路

反轉二元樹，就像拿一個鏡子放在二元樹旁邊，左邊會變成右邊，右邊會變成左邊，而最左邊的節點則會跑到最右邊，反之亦然。

迭代 Iteration & 深度優先搜尋 DFS

透過迭代來解決這個問題可以使用兩種方式，深度優先搜尋DFS和廣度優先搜尋BFS。 DFS使用Stack來排序處理節點的順序。

public class Solution {
	public TreeNode InvertTree(TreeNode root) {
		//邊緣案例 Edge case
		if(root==null) return null;
		//
		var st = new Stack<TreeNode>();
		st.Push(root);
		while(st.Count!=0){
			var n = st.Pop();
			if(n.right!=null) st.Push(n.right);
			if(n.left!=null) st.Push(n.left);
			var tmp = n.left;
			n.left = n.right;
			n.right = tmp;			
		}
		return root;
	}
}

複雜度分析：

• 時間複雜度：每一個節點都需要做左右互換，因此時間複雜度為O(n)。
• 空間複雜度：Stack的堆疊數量取決於樹的深度，最差的情況二元樹可能會是單邊樹，節點數量等於深度，所以空間複雜度是O(n)。

迭代 Iteration & 廣度優先搜尋 BFS

BFS使用Queue來處理。

public class Solution {
	public TreeNode InvertTree(TreeNode root) {
		//邊緣案例 Edge case
		if(root==null) return null;
		//
		var q = new Queue();
		q.Enqueue(root);
		while(q.Count!=0){
			var n = (TreeNode)q.Dequeue();
			if(n.left!=null) q.Enqueue(n.left);
			if(n.right!=null) q.Enqueue(n.right);			
			var tmp = n.left;
			n.left = n.right;
			n.right = tmp;			
		}
		return root;
	}
}

複雜度分析：

• 時間複雜度：每一個節點都需要做左右互換，因此時間複雜度為O(n)。
• 空間複雜度：Queue的數量取決於樹的寬度，最差的情況會是((2^n)/2)個節點寬，而最差情況下的節點數量會是(2^n-1)，((2^n)/2)/(2^n-1)近似於1/2，約花費空間n/2，所以空間複雜度是O(n)。

遞迴 Recursion & 深度優先搜尋 DFS

這一題的節點數量並不多，所以也可以使用遞迴來處理。 概念是一樣的，每一個節點的子節點左右交換，然後將子節點的子節點交由下一個呼叫的函式處理。 DFS專注於先處理單邊的節點。

public class Solution {
	public TreeNode InvertTree(TreeNode root) {
		//邊緣案例 Edge case
        if(root==null) return null;
		//        
        InvertTree(root.left);
        InvertTree(root.right);
		TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }
}

遞迴 Recursion & 廣度優先搜尋 BFS

遞迴的BFS較不一樣的是，需要利用Queue來儲存節點，才能按照BFS的規則來處理節點。
同樣的每處理完一個節點之後，將下一次的處理交給下個呼叫的函式。

public class Solution {
	public TreeNode InvertTree(TreeNode root) {
		//邊緣案例 Edge case
        if(root==null) return null;                
		//
        var q = new Queue();
        q.Enqueue(root);
        Recurse(q);		
        return root;
	}
    public void Recurse(Queue q) {
		//邊界條件
        if(q.Count==0) return;
		//
        var root = (TreeNode) q.Dequeue();        
        if(root.left!=null) q.Enqueue(root.left);
        if(root.right!=null) q.Enqueue(root.right);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        Recurse(q);        
    }
}

學習重點

• 深度優先搜尋DFS和廣度優先搜尋BFS的應用。
• 熟悉樹Tree的特性。