[LeetCode] 226. Invert Binary Tree

問題描述

Invert a binary tree.

Example

翻譯

翻轉這顆二元樹

解題思維

1. 使用 level Order 方式拜訪這顆二元樹，用佇列將每一層  節點儲存起來
2. 同時檢查拜訪該節點是否有左右子樹，若有加入佇列裡面
3. 交換左右節點
4. 重複第二、三步驟直至佇列為空

解題報告

Level: Easy
Time Complexity: O(n)
Runtime: 0 ms, faster than 100.00% of Java online submissions for Invert Binary Tree.
Memory Usage: 37.4 MB, less than 5.10% of Java online submissions for Invert Binary Tree.

程式完整解題

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Queue;
import java.util.LinkedList;
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null)
            return root;

        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();

            if(node.left!=null)
                q.add(node.left);

            if(node.right!=null)
                q.add(node.right);

            TreeNode temp_node = node.left;
            node.left = node.right ;
            node.right = temp_node;
        }
        return root;
    }
}