101 対称二分木

二分木の根ノード root が与えられたとき、木が対称構造か判定する。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return checkNodes(root.left, root.right);
    }
    
    private boolean checkNodes(TreeNode leftNode, TreeNode rightNode) {
        if (leftNode == null && rightNode == null) return true;
        if (leftNode == null || rightNode == null) return false;
        return leftNode.val == rightNode.val 
            && checkNodes(leftNode.left, rightNode.right) 
            && checkNodes(leftNode.right, rightNode.left);
    }
}

反復的解法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root.left);
        queue.add(root.right);
        
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            
            if (left == null && right == null) continue;
            if (left == null || right == null || left.val != right.val) return false;
            
            queue.add(left.left);
            queue.add(right.right);
            queue.add(left.right);
            queue.add(right.left);
        }
        return true;
    }
}

100 同一二分木

二つの二分木の根ノード p と q が与えられたとき、構造と値が完全に同一か判定する。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

111 二分木の最小深度

根ノードから最も近い葉ノードまでの最短経路上のノード数を求める。

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        
        if (root.left == null) return 1 + rightDepth;
        if (root.right == null) return 1 + leftDepth;
        return 1 + Math.min(leftDepth, rightDepth);
    }
}

226 二分木反転

各ノードの左右サブツリーを交換し、反転した木の根ノードを返す。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        
        return root;
    }
}