二叉树相关问题 - 《LeetCode》

LeetCode987 二叉树垂序遍历
二叉树的垂序遍历从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
ps：就是一列一列去输出

思路，dfs记录每个节点的值，横纵坐标，之后排序，遍历排序list一个个输出

public List<List<Integer>> verticalTraversal(TreeNode root) {
    //list集合中的元素是一个数组，每个数组的长度都是3，第1个值表示
    //节点的值，第2个和第3个值表示节点的横坐标和竖坐标
    List<int[]> mList = new ArrayList<>();
    //计算所有节点的值和坐标，根节点的坐标是（0，0）
    dfs(root, 0, 0, mList);
    //排序，排序的原则是先排左边一列，所以首先比较的是数组的第3个值（
    //纵坐标），然后每一列从上到下也就是数组的第2个值（横坐标），如果
    //前面两个值是一样的说明他们的坐标重合了，要按值从大到小排序
    Collections.sort(mList, (arr1, arr2) -> {
        //先按照纵坐标排序
        if (arr1[2] != arr2[2])
            return arr1[2] - arr2[2];
        if (arr1[1] != arr2[1])
            return arr1[1] - arr2[1];
        //如果坐标一样，再按照值排序
        return arr1[0] - arr2[0];
    });
    //把节点的值进行垂序分类
    List<List<Integer>> res = new ArrayList<>();
    res.add(new ArrayList<>());
    //因为上面排序了，所以这里首先遍历的就是最左边一列的值,
    //然后是第二列……
    for (int i = 0; i < mList.size(); i++) {
        //取出数组（包含当前节点的值和坐标）
        int[] arr = mList.get(i);
        //当前节点的值
        int value = arr[0];
        //如果当前节点和前一个节点不在同一列，说明到下一
        //列了，需要初始化下一列的集合
        if (i > 0 && arr[2] != mList.get(i - 1)[2])
            res.add(new ArrayList<>());
        //把当前节点的值添加到当前列中
        res.get(res.size() - 1).add(value);
    }
    return res;
}
private void dfs(TreeNode node, int i, int j, List<int[]> mList) {
    if (node == null)
        return;
    //把当前节点的值和坐标加入到集合中,当前节点的坐标是（i，j）
    mList.add(new int[]{node.val, i, j});
    //遍历左子节点
    dfs(node.left, i + 1, j - 1, mList);
    //遍历右子节点
    dfs(node.right, i + 1, j + 1, mList);
}

LeetCode814 二叉树剪枝就是左子树或者右子树全是0就删掉，思路：DFS从下往上找，是叶子节点且为0就删除

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if(root == null)
            return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.val == 0&& root.left == null&& root.right == null)
            return null;
        return root;
    }
}

LeetCode662 二叉树最大宽度顾名思义
思路：层序遍历BFS时用的单端队列，此题用双端队列Deque，while循环里，每次是一层的在一起，直接peeklast - peekfirst，要额外改变节点的值，父是n，左子就是2n右就是2n+1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null)
            return 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        root.val = 1;
        int maxWide = 0;
        while (!queue.isEmpty()){
            int levelCount = queue.size();
            int left = queue.peekFirst().val;
            int right = queue.peekLast().val;
            maxWide = Math.max(maxWide, right - left + 1);
            for (int i = 0; i < levelCount; i++){
                TreeNode node = queue.poll();
                int position = node.val;
                if (node.left != null){
                    node.left.val = position * 2;
                    queue.offer(node.left);
                }
                if (node.right != null){
                    node.right.val = position * 2 + 1;
                    queue.offer(node.right);
                }
            }
        }
        return maxWide;
    }
}

LeetCode559 N叉树的最大深度
跟二叉树一样DFS，二叉树迭代左右子树，N叉树走个for循环

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public int maxDepth(Node root) {
        if(root == null)
            return 0;
        int size = root.children.size();
        int max = 0;
        for(int i = 0; i < size; i++){
            max = Math.max(max, maxDepth(root.children.get(i)));
        }
        return max + 1;
    }
}

LeetCode230 二叉搜索树第K大的元素 —中序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int target = -1;
    int count;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inOrder(root);
        return target;
    }
    public void inOrder(TreeNode node){
        if(node == null)
            return;
        inOrder(node.left);
        if(--count == 0){
            target = node.val;
            return;
        }
        inOrder(node.right);
    }
}

LeetCode872 叶子相似的树
思路：DFS把叶子储存起来，可以用list或者stringBuilder然后比较就行了

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        dfs(root1, sb1);
        dfs(root2, sb2);
        return sb1.toString().equals(sb2.toString());
    }
    private void dfs(TreeNode root, StringBuilder sb){
        if(root == null)
            return;
        if(root.left == null&& root.right == null){
            sb.append(root.val + "#");
            return;
        }
        dfs(root.left, sb);
        dfs(root.right, sb);
    }
}

LeetCode938 二叉搜索树范围和，顾名思义，给定范围将在范围内的累加
利用搜索树的特点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if(root == null)
            return 0;
        if(root.val > high)
            return rangeSumBST(root.left, low, high);
        if(root.val < low)
            return rangeSumBST(root.right, low, high);
        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }
}

LeetCode 110 平衡二叉树
弱智题DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null)
            return true;
        int left = deepth(root.left);
        int right = deepth(root.right);
        return Math.abs(left - right) <= 1&& isBalanced(root.right)&& isBalanced(root.left);
    }
    public int deepth(TreeNode node){
        if(node == null)
            return 0;
        return Math.max(deepth(node.left), deepth(node.right)) + 1;
    }
}

LeetCode108 有序数组转换二叉搜索树
找中间左右迭代，DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null|| nums.length == 0)
            return null;
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }
    public TreeNode sortedArrayToBST(int[] nums, int start, int end){
        if(start > end)
            return null;
        int mid = (start + end) >> 1;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBST(nums, start, mid - 1);
        node.right = sortedArrayToBST(nums, mid + 1, end);
        return node;
    }
}

LeetCode501 二叉搜索树众数
中序遍历，在dfs时判断当前值与前一个值得关系，不断更新list

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList<>();
    int count;
    int cur;
    int max;
    public int[] findMode(TreeNode root) {
        inOrder(root);
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }
    private void inOrder(TreeNode root){
        if(root == null)
            return;
        inOrder(root.left);
        int rootVal = root.val;
        if(rootVal == cur){
            count++;
        }else{
            cur = rootVal;
            count = 1;
        }
        if(count == max){
            list.add(cur);
        }else if(count > max){
            max = count;
            list.clear();
            list.add(cur);
        }
        inOrder(root.right);
    }
}

二叉树莫里斯前序中序遍历
中序步骤：

1 public List<Integer> inorderTraversal(TreeNode root) {
    2 List<Integer> res = new ArrayList<>();
    3 //首先把根节点赋值给cur
        4 TreeNode cur = root;
    5 //如果cur不为空就继续遍历
        6 while (cur != null) {
            7 if (cur.left == null) {
                8 //如果当前节点cur的左子节点为空，就访问当前节点cur，
                    9 //接着让当前节点cur指向他的右子节点
                    10 res.add(cur.val);
                11 cur = cur.right;
                12 } else {
                13 TreeNode pre = cur.left;
                14 //查找pre节点，注意这里有个判断就是pre的右子节点不能等于cur
                    15 while (pre.right != null && pre.right != cur)
                        16 pre = pre.right;
                17 //如果pre节点的右指针指向空，我们就让他指向当前节点cur，
                    18 //然后当前节点cur指向他的左子节点
                    19 if (pre.right == null) {
                        20 pre.right = cur;
                        21 cur = cur.left;
                        22 } else {
                        23 //如果pre节点的右指针不为空，那么他肯定是指向cur的,
                            24 //表示cur的左子节点都遍历完了，我们需要让pre的右
                            25 //指针指向null，目的是把树给还原，然后再访问当前节点
                            26 //cur，最后再让当前节点cur指向他的右子节点。
                            27 pre.right = null;
                        28 res.add(cur.val);
                        29 cur = cur.right;
                        30 }
                31 }
            32 }
    33 return res;
34 }

1，判断cur是否为空，如果为空就停止遍历。
2，如果cur不为空
1 ）如果 cur 没有左子节点，打印 cur 的值，然后让 cur 指向他的右子节点，即
cur=cur.right
2）如果cur有左子节点，则从左子节点中找到最右边的结点pre。
1))如果pre的右子节点为空，就让pre的右子节点指向cur，即pre.right=cur，
然后cur指向他的左子节点，即cur=cur. left。
2))如果pre的右子节点不为空，就让他指向空，即pre.right=nul l，然后输出cur
节点的值，并将节点cur指向其右子节点，即cur=cur.right。
3，重复步骤2，直到节点cur为空为止。
前序：

1 public List<Integer> preorderTraversal(TreeNode root) {
    2 List<Integer> res = new ArrayList<>();
    3 //首先把根节点赋值给cur
        4 TreeNode cur = root;
    5 //如果cur不为空就继续遍历
        6 while (cur != null) {
            7 if (cur.left == null) {
                8 //如果当前节点cur的左子节点为空，就访问当前节点cur，
                    9 //接着让当前节点cur指向他的右子节点
                    10 res.add(cur.val);
                11 cur = cur.right;
                12 } else {
                13 TreeNode pre = cur.left;
                14 //查找pre节点，注意这里有个判断就是pre的右子节点不能等于cur
                    15 while (pre.right != null && pre.right != cur)
                        16 pre = pre.right;
                17 //如果pre节点的右指针指向空，我们就让他指向当前节点cur，
                    18 //然后打印当前节点cur的值，最后再让当前节点cur指向他的左子节点
                    19 if (pre.right == null) {
                        20 pre.right = cur;
                        21 res.add(cur.val);
                        22 cur = cur.left;
                        23 } else {
                        24 //如果pre节点的右指针不为空，那么他肯定是指向cur的,
                            25 //表示当前节点cur和他的的左子节点都遍历完了，直接
                            26 //让他指向他的右子节点即可。
                            27 pre.right = null;
                        28 cur = cur.right;
                        29 }
                30 }
            31 }
    32 return res;
33 }

LeetCode100 相同的树即判断两棵树是否完全相同
DFS判断即可

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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);
    }
}

LeetCode222 完全二叉树节点个数

class Solution {
    public int countNodes(TreeNode root) {
        return root == null ? 0 : countNodes(root.left) + countNodes(root.right) + 1;
    }
}

class Solution {
    public int countNodes(TreeNode root) {
        int high = deepth(root);
        if(high == 0|| high == 1)
            return high;
        if(deepth(root.right) == high - 1){
            return (1<<(high - 1)) + countNodes(root.right);
        }else{
            return countNodes(root.left) + (1<<(high - 2));
        }
    }
    private int deepth(TreeNode root){
        return root == null? 0: deepth(root.left) + 1;
    }
}

LeetCode226 翻转二叉树
DFS即可，就跟交换两个数是一样的道理

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

        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

LeetCode701 二叉搜索树插入操作
见到二叉搜索树基本就是DFS中序离不开，跟范围和那道题一样判断属于左子树还是右子树直接迭代就可以

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        } else {
            root.left = insertIntoBST(root.left, val);
        }
        return root;
    }
}

LeetCode257 二叉树所有路径
DFS遍历从上到下

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        if(root == null)
            return list;
        dfs(root, "", list);
        return list;
    }
    public void dfs(TreeNode root, String path, List<String> list){
        if(root.left == null&& root.right == null)
            list.add(path + root.val);
        if(root.left != null)
            dfs(root.left, path + root.val + "->", list);
        if(root.right != null)
            dfs(root.right, path + root.val + "->", list);
    }
}

LeetCode116 填充每个节点的右侧节点
就是将二叉树的每一行连起来，所以是BFS

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if(root == null)
            return null;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int cueSize = queue.size();
            Node pre = null;
            for(int i = 0; i < cueSize; i++){
                Node cur = queue.poll();
                if(pre != null)
                    pre.next = cur;
                pre = cur;
                if(cur.left != null)
                    queue.add(cur.left);
                if(cur.right != null)
                    queue.add(cur.right);
            }
        }
        return root;
    }
}

LeetCode剑指offer68 二叉搜索树最近公共祖先
判断两节点值与根节点值得大小即可

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if((root.val - p.val)*(root.val - q.val) <= 0)
            return root;
        return lowestCommonAncestor(p.val < root.val? root.left: root.right, p, q);
    }
}

二叉树的最近公共祖先，还是DFS迭代

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null; // 如果树为空，直接返回null
        if(root == p || root == q) return root; // 如果 p和q中有等于 root的，那么它们的最近公共祖先即为root（一个节点也可以是它自己的祖先）
        TreeNode left = lowestCommonAncestor(root.left, p, q); // 递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁
        TreeNode right = lowestCommonAncestor(root.right, p, q); // 递归遍历右子树，只要在右子树中找到了p或q，则先找到谁就返回谁
        if(left == null) return right; // 如果在左子树中 p和 q都找不到，则 p和 q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
        else if(right == null) return left; // 否则，如果 left不为空，在左子树中有找到节点（p或q），这时候要再判断一下右子树中的情况，如果在右子树中，p和q都找不到，则 p和q一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
        else return root; //否则，当 left和 right均不为空时，说明 p、q节点分别在 root异侧, 最近公共祖先即为 root
    }
}

LeetCode199 二叉树右视图
需要一行行的肯定是BFS的，每一行的最后一个也就是curSize == 0的时候

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()){
            int count = queue.size();
            while (count-- > 0){
                TreeNode cur = queue.poll();
                if (count == 0)
                    res.add(cur.val);
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
            }
        }
        return res;
    }
}

二叉树序列化与反序列化
DFS与BFS都可以，BFS从代码逻辑上更好理顺

public class Codec {
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

判断序列是否是二叉搜索树后序遍历结果
思路：最后一个是根节点，左侧的比根小，右侧的比根大，迭代即可

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return helper(postorder, 0, postorder.length - 1);
    }
    boolean helper(int[] postorder, int left, int right){
        if (left >= right)
            return true;
        int mid = left;
        int root = postorder[right];
        while (postorder[mid] < root)
            mid++;
        int temp = mid;
        while (temp < right){
            if (postorder[temp++] < root)
                return false;
        }
        return helper(postorder, left, mid - 1) && helper(postorder, mid, right - 1);
    }
}

从上到下打印二叉树，结果只需要一个数组时

public int[] levelOrder(TreeNode root) {
    if (root == null)
        return new int[0];
    //队列
    Queue<TreeNode> queue = new LinkedList<>();
    List<Integer> list = new ArrayList<>();
    //根节点入队
    queue.add(root);
    while (!queue.isEmpty()) {
        //出队
        TreeNode node = queue.poll();
        //把结点值存放到list中
        list.add(node.val);
        //左右子节点如果不为空就加入到队列中
        if (node.left != null)
            queue.add(node.left);
        if (node.right != null)
            queue.add(node.right);
    }
    //把list转化为数组
    int[] res = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        res[i] = list.get(i);
    }
    return res;
}

一次一行结果是list时

    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }

之字形打印时

    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶数层 -> 队列头部
                else tmp.addFirst(node.val); // 奇数层 -> 队列尾部
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }

LeetCode101 对称二叉树，判断二叉树是否完全对称
DFS即可，迭代判断，左左右右，左右右左

    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        return isSymmetricHelper(root.left, root.right);
    }
    public boolean isSymmetricHelper(TreeNode left, TreeNode right){
        if (left == null && right == null)
            return true;
        if (left == null || right == null || left.val != right.val)
            return false;
        return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
    }

二叉树镜像
递归随便选个遍历方式即可

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

判断B树是否是A树的子结构
递归判断即可

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null)
            return false;
        return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    boolean isSub(TreeNode A, TreeNode B){
        if (B == null)
            return true;
        if (A == null || A.val != B.val)
            return false;
        return isSub(A.left, B.left) && isSub(A.right, B.right);
    }

LeetCode105 前序中序重建二叉树
前序【0】是根，在中序中找到位置递归即可

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        List<Integer> preorderList = new ArrayList<>();
        List<Integer> inorderList = new ArrayList<>();
        for (int i = 0; i < preorder.length; i++){
            preorderList.add(preorder[i]);
            inorderList.add(inorder[i]);
        }
        return helper(preorderList, inorderList);
    }
    private TreeNode helper(List<Integer> preorderList, List<Integer> inorderList){
        if (inorderList.size() == 0)
            return null;
        int rootVal = preorderList.remove(0);
        TreeNode root = new TreeNode(rootVal);
        //找到中序中根的位置
        int mid = inorderList.indexOf(rootVal);
        root.left = helper(preorderList, inorderList.subList(0, mid));
        root.right = helper(preorderList, inorderList.subList(mid + 1, inorderList.size()));
        return root;
    }

LeetCode98 验证是否二叉搜索树
中序是否递增即可

    TreeNode prev;
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        if (!isValidBST(root.left))
            return false;
        if (prev != null && prev.val >= root.val)
            return false;
        prev = root;
        if (!isValidBST(root.right))
            return false;
        return true;
    }

LeetCode450 删除二叉搜索树中的节点
如果要删除的节点是叶子节点，我们直接删除即可。
如果删除的结点不是叶子节点，并且有一个子节点为空，我们直接返回另一个不为
空的子节点即可。
如果删除的结点不是叶子节点，并且左右子树都不为空，我们可以用左子树的最大
值替换掉要删除的节点或者用右子树的最小值替换掉要删除的节点都是可以的。

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return null;
        if (key < root.val){
            root.left = deleteNode(root.left, key);
        } else if (key > root.val){
            root.right = deleteNode(root.right, key);
        } else{
            if (root.left == null)
                return root.right;
            if(root.right == null)
                return root.left;
            else{
                TreeNode maxNode = findMax(root.left);
                root.val = maxNode.val;
                root.left = deleteNode(root.left, root.val);
            }
        }
        return root;
    }
    private TreeNode findMax(TreeNode node){
        while (node.right != null)
            node = node.right;
        return node;
    }

LeetCode1008 给定先序数组，还原二叉搜索树
确定根之后后面每个值递归插入即可

    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 1; i < preorder.length; i++){
            addTreeNode(root, preorder[i]);
        }
        return root;
    }   
    private TreeNode addTreeNode(TreeNode root, int val){
        if (root == null)
            return new TreeNode(val);
        else if (root.val > val)
            root.left = addTreeNode(root.left, val);
        else    
            root.right = addTreeNode(root.right, val);
        return root;
    }

LeetCode124 二叉树最大路径和
递归判断左右子树各自最大路径和

    private int maxValue = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPathSumHelper(root);
        return maxValue;
    }
    public int maxPathSumHelper(TreeNode root){
        if (root == null)
            return 0;
        int left = maxPathSumHelper(root.left);
        int right = maxPathSumHelper(root.right);
        int cur = root.val + Math.max(0, left) + Math.max(0, right);
        int res = root.val + Math.max(0, Math.max(left, right));
        maxValue = Math.max(maxValue, Math.max(cur, res));
        return res;
    }

二叉树每一层的最大值
bfs时每一层更新一个max

public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> values = new ArrayList<>();
        if (root != null)
            queue.add(root);
        while (!queue.isEmpty()){
            int max = Integer.MIN_VALUE;
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++){
                TreeNode node = queue.poll();
                max = Math.max(max, node.val);
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            values.add(max);
        }
        return values;
    }

LeetCode111 二叉树最小深度
跟深度高度相关的还是DFS递归简单些

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

LeetCode104最大深度

    public int maxDepth(TreeNode root) {
        if (root == null) 
            return 0; 
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }