手动构造LeetCode的输入——二叉树

在面试的时候，二叉树类题目出现频率也非常高，我遇到过很多经典题目，比如两棵二叉树的最近公共祖先、判断一棵二叉树是否是另一棵的子结构、二叉树的最大宽度、深度、直径……为了验证算法准确性，我们需要自行构造二叉树的数据并向面试官解释。构造二叉树要比链表更加麻烦，可以参考本实现。

import java.util.LinkedList;
import java.util.Queue;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

    public static TreeNode buildTree(Integer[] arr) {
        TreeNode root = new TreeNode(arr[0]);
        Queue<TreeNode> q = new LinkedList<>();
        int cur = 1;
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode r = q.poll();
            if (arr[cur] == null) {
                r.left=null;
            } else {
                r.left = new TreeNode(arr[cur]);
                q.offer(r.left);
            }
            if (++cur >= arr.length) {
                break;
            }
            if (arr[cur] == null) {
                r.right = null;
            } else {
                r.right = new TreeNode(arr[cur]);
                q.offer(r.right);
            }
            if (++cur >= arr.length) {
                break;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = buildTree(new Integer[]{3, 5});
        dfs(root);
    }

    public static void dfs(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        dfs(root.left);
        dfs(root.right);
    }
}