LeetCode刷题学习-二叉树篇

二叉树递归遍历

二叉树结点数据结构定义如下：

package cycle;

/**
 * 二叉树节点的数据结构
 */
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;
    }
}

1. 前序

package cycle;

import java.util.ArrayList;
import java.util.List;

/**
 * 递归前序遍历
 * https://leetcode.cn/problems/binary-tree-preorder-traversal/
 */
public class PreOrderCycle {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode root2 = new TreeNode(2);
        TreeNode root3 = new TreeNode(3);
        root.left = null;
        root.right = root2;
        root2.left = root3;
        System.out.println( new PreOrderCycle().preorderTraversal(root));
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        preOrder(root, list);
        return list;
    }

    public void preOrder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        list.add(root.val);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }
}

2. 中序

package cycle;

import java.util.ArrayList;
import java.util.List;

/**
 * 中序递归遍历
 * https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/
 */
public class InOrderCycle {
    public List<Integer> inOrderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        inOrder(root, list);
        return list;
    }

    public void inOrder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }
}

3. 后序

package cycle;

import java.util.ArrayList;
import java.util.List;

/**
 * 后序递归遍历
 * https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/
 */
public class PostOrderCycle {
    public List<Integer> postOrderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        postOrder(root, list);
        return list;
    }

    public void postOrder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        postOrder(root.left, list);
        postOrder(root.right, list);
        list.add(root.val);
    }
}

二叉树非递归遍历

利用栈

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 List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        
        ArrayList<Integer> list = new ArrayList<>();
		// 先访问结点，然后入栈，先把左边的所有结点访问完；当左边访问完毕，栈中元素出栈，访问其右孩子，直至遍历完毕
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                list.add(root.val);
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                root = root.right;
            }
        }
        return 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 Solution2 {
    // 入栈顺序为：中-右-左，出栈顺序：中-左-右
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        
        if (root == null) return list;

        Stack<TreeNode> stack = new Stack<>();

        // 先把根节点入栈
        stack.push(root);

        // 栈非空，循环继续
        while (!stack.isEmpty()) {
            // 栈顶元素出栈
            TreeNode node = stack.pop();
            // 访问元素值
            list.add(node.val);
            // 右孩子非空，入栈
            if(node.right != null) {
                stack.push(node.right);
            }
			// 左孩子非空，入栈
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return list;
    }
}

2. 中序

与前序基本一致，只是访问元素值位置不一致

public List<Integer> inorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    ArrayList<Integer> list = new ArrayList<>();

    while (root != null || !stack.isEmpty()) {
        if (root != null) {
            stack.push(root);
            root = root.left;
        } else {
            root = stack.pop();
            // 访问元素值
            list.add(root.val);
            root = root.right;
        }
    }
    return list;
}

3. 后序

大致框架与前中序类似，但代码细节有一定的变动

package nocycle;

import cycle.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PostOrder {

    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();

        // 标记右孩子是否访问过
        TreeNode rightFlag = null;

        // 与前序和中序类似
        while (root != null || !stack.isEmpty()) {
            // 不为null，入栈并一直往左
            if (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 到最左边时
            else {
                // 获取栈顶元素
                root = stack.peek();
                // 当其存在右孩子且未被访问过时，往右孩子方向走
                if (root.right != null && root.right != rightFlag) {
                    root = root.right;
                } else {
                    // 否则直接pop出栈顶元素并访问其值
                    root = stack.pop();
                    list.add(root.val);
                    // 标记右孩子已是被访问过的
                    rightFlag = root;
                    // 置为null方便继续pop出栈顶元素
                    root = null;
                }
            }
        }
        return list;
    }
}

4. 层序

利用队列的特性，当结点出队的时候就访问其左右孩子并入队，直至队列为空

常规：

public static List<Integer> levelorder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    ArrayList<Integer> list = new ArrayList<>();

    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        list.add(node.val);
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    return list;
}

变化后：

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> resultList = new ArrayList<>();
    if (root == null) return resultList;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        // 在每次出队之前记录下当前队列结点个数，因为此时队列中的结点都是同一层的
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        // 批量处理同一层的结点
        for (int i = 0; i < size; i++) {
            // 出队
            TreeNode node = queue.poll();
            // 访问
            list.add(node.val);
            // 左孩子入队
            if (node.left != null) {
                queue.add(node.left);
            }
            // 右孩子入队
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        resultList.add(list);
    }
    return resultList;
}

翻转二叉树

1. 非递归：BFS

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    // 左右子树交换，利用队列存储当前左右子树的父节点
    while (!queue.isEmpty()) {
        // 每次出队的都是当前的父节点
        TreeNode node = queue.poll();
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        if(node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    // 返回翻转后的根节点
    return root;
}

2. 递归：DFS

public TreeNode invertTreeCycle(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    invertTreeCycle(root.left);
    invertTreeCycle(root.right);
    return root;
}

对称二叉树

1. 递归

public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return dfs(root.left, root.right);
    }

    /**
     * @param left 左子树
     * @param right 右子树
     * @return
     */
    public boolean dfs(TreeNode left, TreeNode right) {
        // 当左右子树均为空时，对称
        if(left == null && right == null) return true;
        // 当左右子树只有一边为空时，不对称
        if(left == null || right == null) return false;
        // 当左右子树两边均不为空时，比较其值，值不等则不对称
        if (left.val != right.val) return false;
        // 比较两边的值是否相等，比较方法：左子树的左孩子与右子树的右孩子比较；左子树的右孩子与右子树的左孩子比较；相等则对称
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }

2. 非递归：利用队列实现（BFS）

public boolean isSymmetric(TreeNode root) {
    // 无根节点或只有一个根节点时，对称
    if (root == null || (root.left == null && root.right == null)) return true;
    Queue<TreeNode> queue = new LinkedList<>();
    // 先将左右子树入队
    queue.add(root.left);
    queue.add(root.right);
    // 当队列非空
    while (!queue.isEmpty()) {
        // 左右子树一起出队
        TreeNode left = queue.poll();
        TreeNode right = queue.poll();
        // 当两个左右子树均为null时，继续循环找下去，直至队列为空
        if (left == null && right == null) continue;
        // 当左右子树只有一个为null时，不对称，直接false
        if (left == null || right == null) return false;
        // 当左右子树均不为null，但其值不等，也不对称
        if (left.val != right.val) return false;

        // 左右子树均不为null，需要比较其值是否相等，比较：左子树的左孩子和右子树的右孩子；左子树的右孩子和右子树的左孩子
        queue.add(left.left);
        queue.add(right.right);
        queue.add(left.right);
        queue.add(right.left);
    }
    // 最后队列处理完毕说明对称
    return true;
}

二叉树最大深度

补充：

深度：由上往下，前序遍历
高度：由下往上，后序遍历

参考视频：二叉树最大深度

1. 递归

public class Solution {
    /**
     * 获取二叉树的最大深度 = MAX（左子树深度， 右子树深度） + 1
     * +1是把当前节点算进去
     */
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        // 找左子树最大深度
        int leftDepth = maxDepth(root.left);
        // 找右子树最大深度
        int rightDepth = maxDepth(root.right);
        // 最终找两者最大值
        return Math.max(leftDepth, rightDepth) + 1;
    }

}

2. 非递归：与层序遍历差不多，每次处理完同一层的结点后深度+1

public int bfs(TreeNode root) {
    if (root == null) return 0;
    // 用于记录最大深度
    int result = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        // 每次都处理同一层的结点
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        // 处理完一层深度+1
        result++;
    }
    return result;
}

二叉树最小深度

此题误区：很容易误以为与求最大深度一样，只是取左右子树深度之间的最小值即可

注意：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

1. 非递归

public int minDepth(TreeNode root) {
    if (root == null) return 0;
    // 依然是层序遍历那套模板修改一下
    int depth = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        depth++;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode curNode = queue.poll();
            // 当前结点的左右孩子均为空的时候说明其是叶子结点，直接返回depth就是当前最小深度
            if (curNode.left == null && curNode.right == null) return depth;
            if (curNode.left != null) queue.add(curNode.left);
            if (curNode.right != null) queue.add(curNode.right);
        }
    }
    return depth;
}

2. 递归

public int dfs(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;
	// 最后取左右子树最小深度最小值 + 1（当前结点）
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

完全二叉树的节点个数

1. 非递归

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int count = 0;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        count += size;
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
    }
    return count;
}

2. 递归

public int dfs(TreeNode root) {
    if (root == null) return 0;
    // 左子树所有节点 + 右子树所有节点 + 根节点
    return dfs(root.left) + dfs(root.right) + 1;
}

平衡二叉树

平衡二叉树：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

递归：

public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    /**
     * 递归左子树的最大高度，
     * 递归右子树的最大高度
     * 作差求|BF| 若|BF|<=1则为平衡二叉树，返回-1则不是平衡二叉树
     */
    public int getHeight(TreeNode root) {
        if (root == null) return 0;

        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) return -1;

        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) return -1;

        if (Math.abs(rightHeight - leftHeight) > 1) return -1;
        // 求最大高度
        return Math.max(rightHeight, leftHeight) + 1;
    }

二叉树的所有路径

1. 非递归

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 在层序遍历的基础上做出变化
 * 队列存储的是Object，刚好可以令节点及其路径成对入队和出队
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> result = new ArrayList<>();
        if (root == null) return result;

        Queue<Object> queue = new LinkedList<>();
        // 根节点入队
        queue.add(root);
        // 根节点路径
        queue.add(root.val + "");
        while (!queue.isEmpty()) {
            // 节点出队
            TreeNode node = (TreeNode) queue.poll();
            // 相应的路径跟着出队
            String path = (String) queue.poll();
            // 当去到叶子节点时，证明此条路径已完整，将其存储起来
            if (node.left == null && node.right == null) result.add(path);
            // 左子树还有继续遍历
            if (node.left != null) {
                queue.add(node.left);
                // 不断完善路径，直至到叶子节点
                queue.add(path + "->" + node.left.val);
            }
            // 右子树还有继续遍历
            if (node.right != null) {
                queue.add(node.right);
                queue.add(path + "->" + node.right.val);
            }
        }
        return result;
    }
}

2. 递归

public void dfs(TreeNode root, String path, List<String> result) {
    if (root == null) return;
    // 叶子节点，将完整路径存储
    if (root.left == null && root.right == null){
        result.add(path + root.val);
        return;
    }
    // 分别遍历左右子树
    dfs(root.left, path + root.val + "->", result);
    dfs(root.right, path + root.val + "->", result);
}

左叶子之和

如何判断当前节点是否是左叶子节点呢？必须通过其父节点来判断其左孩子是否是叶子节点

1. 非递归

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null || (root.left == null && root.right == null)) return 0;

    int sum = 0;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 存在左孩子
            if (node.left != null) {
                // 左孩子入队
                queue.add(node.left);
                // 则其左孩子是否是叶子节点呢？若是，则计算求和
                if (node.left.left == null && node.left.right == null) sum+=node.left.val;
            }
            // 右孩子正常入队，不做特别处理
            if (node.right != null) queue.add(node.right);
        }

    }
    return sum;
}

2. 递归

int res = 0;
public int dfs(TreeNode root) {
    if (root == null) return 0;
    // 存在左孩子，同时其左孩子是叶子节点，则将结果加入结果集
    if (root.left != null && root.left.left == null && root.left.right == null) {
        res += root.left.val;
    }
    // 找左子树的左叶子节点和
    dfs(root.left);
    // 找右子树的左叶子节点和
    dfs(root.right);
    // 返回最终结果
    return res;
}

找树左下角的值

找出二叉树最底层，最左边节点的值，其实就是最后一层，从左往右的第一个节点的值

1. 非递归

public int findBottomLeftValue(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return root.val;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int result = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            // 更新结果为每一层的第一个节点的值
            if (i == 0) result = queue.peek().val;
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) queue.add(node.right);
        }
    }
    return result;
}

路径总和

1. 非递归

可以采用与求二叉树所有路径类似的方法

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;

    Queue<Object> queue = new LinkedList<>();
    List<Integer> list = new ArrayList<>();
    queue.add(root);
    queue.add(root.val);
    while (!queue.isEmpty()) {
        TreeNode node = (TreeNode) queue.poll();
        int sum = (int) queue.poll();
        if (node.left == null && node.right == null) {
            list.add(sum);
        }
        if (node.left != null) {
            queue.add(node.left);
            queue.add(sum + node.left.val);
        }
        if (node.right != null) {
            queue.add(node.right);
            queue.add(sum + node.right.val);
        }
    }
    for (Integer item : list) {
        if (item == targetSum) return true;
    }
    return false;
}