刷题顺序来自：代码随想录

目录

• 二叉树的递归遍历
  • 144. 二叉树的前序遍历
  • 145. 二叉树的后序遍历
  • 94. 二叉树的中序遍历
• 二叉树的迭代遍历
  • 144. 二叉树的前序遍历
  • 145. 二叉树的后序遍历
  • 94. 二叉树的中序遍历
• 二叉树层序遍历
  • 102. 二叉树的层序遍历
  • 107. 二叉树的层序遍历 II
  • 199. 二叉树的右视图
  • 637. 二叉树的层平均值
  • 429. N 叉树的层序遍历
  • 515. 在每个树行中找最大值
  • 116. 填充每个节点的下一个右侧节点指针
  • 117. 填充每个节点的下一个右侧节点指针 II
• 翻转二叉树
  • 226. 翻转二叉树
    • 递归
    • 广度优先
    • 深度优先
• 对称二叉树
  • 101. 对称二叉树
  • 100. 相同的树
  • 572. 另一棵树的子树
• 二叉树的深度
  • 104. 二叉树的最大深度
  • 559. N 叉树的最大深度
  • 111. 二叉树的最小深度
    • 递归
    • 迭代
• 完全二叉树节点个数
  • 222. 完全二叉树的节点个数
    • 递归
    • 迭代
• 平衡二叉树
  • 110. 平衡二叉树
    • 自顶向下递归
    • 递归优化
• 二叉树的所有路径
  • 257. 二叉树的所有路径
    • 递归

二叉树的递归遍历

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

public List preorderTraversal(TreeNode root) {
    ArrayList list = new ArrayList<>();
    preOrder(list, root);

    return list;
}

private void preOrder(ArrayList list, TreeNode root) {
    if(root!=null) {
        list.add(root.val);
        preOrder(list, root.left);
        preOrder(list, root.right);
    }
}

145. 二叉树的后序遍历

    public List postorderTraversal(TreeNode root) {
        ArrayList list  = new ArrayList<>();
        postOrder(list, root);

        return list;
    }

    private void postOrder(ArrayList list, TreeNode root) {
        if(root != null) {
            postOrder(list, root.left);
            postOrder(list, root.right);
            list.add(root.val);
        }
    }

94. 二叉树的中序遍历

public List inorderTraversal(TreeNode root) {
    ArrayList list = new ArrayList<>();
    inOrder(list, root);

    return list;
}

private void inOrder(ArrayList list, TreeNode root) {
    if(root != null) {
        inOrder(list, root.left);
        list.add(root.val);
        inOrder(list, root.right);
    }
}

二叉树的迭代遍历

144. 二叉树的前序遍历

弹出栈顶元素，输出栈顶的值，压入右节点、左节点。

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

    if(root != null) {
        stack.push(root);
    }

    while(!stack.empty()) {
        TreeNode node = stack.pop();
        if(node.right != null) {
            stack.push(node.right);
        }
        if(node.left != null) {
            stack.push(node.left);
        }
        list.add(node.val);
    }

    return list;
}

可以采取统一风格的写法，其主要思想是：

• 当栈顶元素没有被访问过，将栈顶元素弹出，按倒序压入(例如前序，那就按右左中的顺序压入)，并且在压入中节点(当前节点)时，在其后压入null表示该节点已经被访问过了
• 当栈顶元素为null，表示该节点被访问过，连续弹出2次并输出值

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

    if(root != null) {
        stack.push(root);
    }

    while(!stack.empty()) {
        if(stack.peek() != null) {
            TreeNode node = stack.pop();
            if(node.right != null) {
                stack.push(node.right);
            }
            if(node.left != null) {
                stack.push(node.left);
            }
            stack.push(node);
            stack.push(null);
        }
        else {
            stack.pop();
            list.add(stack.pop().val);
        }
    }

    return list;
}

145. 二叉树的后序遍历

弹出节点栈顶元素，压入左节点、右节点，将栈顶元素压入输出栈。依次弹出输出栈的值。

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

    Stack nodeStack = new Stack<>();
    Stack outputStack = new Stack<>();

    if(root != null) {
        nodeStack.push(root);
    }

    while(!nodeStack.empty()) {
        TreeNode node = nodeStack.pop();
        if(node.left != null) {
            nodeStack.push(node.left);
        }
        if(node.right != null) {
            nodeStack.push(node.right);
        }            
        outputStack.push(node.val);
    }

    while(!outputStack.empty()) {
        list.add(outputStack.pop());
    }

    return list;
}

94. 二叉树的中序遍历

一直向栈中压左节点直到当前节点为空，弹出栈顶节点，压右节点，重复。

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

    Stack stack = new Stack<>();

    if(root != null) {
        stack.push(root);
    }

    TreeNode curr = root;
    while(!stack.empty()) {
        if(curr != null) {
            curr = curr.left;
        }
        else {
            curr = stack.pop();
            list.add(curr.val);
            curr = curr.right;
        }
        if(curr != null) {
            stack.push(curr);
        }
    }

    return list;
}

二叉树层序遍历

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

主要思想是通过FIFO的队列遍历。

public List> levelOrder(TreeNode root) {
    ArrayList> res = new ArrayList<>();
    LinkedList currLayer = new LinkedList<>();

    if(root != null) {
        currLayer.add(root);
    }
	
    // 每次循环遍历一层
    while(currLayer.size() != 0) {
        currLayer.add(null);  // 在当前层最后加一个null的标志
        ArrayList list = new ArrayList<>(); // 存储当前层遍历的结果
		
        // 除了加null标志，还可以控制循环次数等于currLayer.size()
        while(currLayer.getFirst() != null) {
            TreeNode node = currLayer.removeFirst();
            list.add(node.val);
            
            // 左右节点添加到队尾(与当前层有null标志隔开)
            if(node.left != null) {
                currLayer.add(node.left);
            } 
            if(node.right != null) {
                currLayer.add(node.right);
            }
        }
        currLayer.removeFirst();  // 移除之前添加的null标志

        res.add(list);  // 存储当前层的遍历结果
    }

    return res;
}

通过递归的方式遍历。

public List> levelOrder(TreeNode root) {
    ArrayList> res = new ArrayList<>();
    level(res, root, 1);

    return res;
}

private void level(List> res, TreeNode node, int deep) {
    if(node == null) return;
	
    // 当前节点是该层第一个节点，需要实例化一个数组
    if(res.size() < deep) {
        res.add(new ArrayList());
    }

    res.get(deep-1).add(node.val);

    level(res, node.left, deep+1);
    level(res, node.right, deep+1);
}

107. 二叉树的层序遍历 II

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。

和上一题类似，只需要把输出结果在栈中反转即可，或者直接调用Collections.reverse()方法。

public List> levelOrderBottom(TreeNode root) {
    ArrayList> res = new ArrayList<>();
    LinkedList currLayer = new LinkedList<>();

    if(root == null) {
        return res;
    }
    else {
        currLayer.add(root);
    }

    Stack> outputStack = new Stack<>();  // 
    while(currLayer.size() != 0) {
        int count = currLayer.size();
        ArrayList list = new ArrayList<>();

        for(int i = 0; i < count; i++) {
            TreeNode node = currLayer.removeFirst();
            list.add(node.val);
            if(node.left != null) {
                currLayer.add(node.left);
            }
            if(node.right != null) {
                currLayer.add(node.right);
            }
        }

        outputStack.push(list);  // 先将输出结果放入栈
    }

    // 输出结果反转
    while(!outputStack.empty()) {
        res.add(outputStack.pop());
    }

    return res;
}

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

public List rightSideView(TreeNode root) {
    ArrayList res = new ArrayList<>();
    LinkedList currLayer = new LinkedList<>();

    if(root == null) {
        return res;
    }
    else {
        currLayer.add(root);
    }

    while(currLayer.size() > 0) {
        int len = currLayer.size();

        for(int i = 0; i < len; i++) {
            TreeNode node = currLayer.removeFirst();
            if(node.left != null) {
                currLayer.add(node.left);
            }
            if(node.right != null) {
                currLayer.add(node.right);
            }
            
            // 添加最右侧节点的值
            if(i == len - 1) {
                res.add(node.val);
            }
        }
    }
    return res;
}

637. 二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

public List averageOfLevels(TreeNode root) {
    ArrayList res = new ArrayList<>();
    LinkedList currLayer = new LinkedList<>();

    if(root != null) {
        currLayer.add(root);
    }

    while(currLayer.size() != 0) {
        int len = currLayer.size();
        double sum = 0;  // 当前层累加和
        for(int i = 0; i < len; i++) {
            TreeNode node = currLayer.removeFirst();

            if(node.left != null) {
                currLayer.add(node.left);
            }
            if(node.right != null) {
                currLayer.add(node.right);
            }

            sum += node.val;
        }
        res.add(sum / len);
    }

    return res;
}

429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

public List> levelOrder(Node root) {
    ArrayList> res = new ArrayList<>();
    LinkedList currLayer = new LinkedList<>();

    if(root != null) {
        currLayer.add(root);
    }

    while(currLayer.size() != 0) {
        int len = currLayer.size();
        ArrayList list = new ArrayList<>();

        for(int i = 0; i < len; i++) {
            Node node = currLayer.removeFirst();
            list.add(node.val);
			
            // 将孩子节点依次加入队列
            List children = node.children;
            if(children != null) {
                for(Node child: children) {
                    currLayer.add(child);
                }
            }
        }
        res.add(list);
    }
    return res;
}

515. 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

public List largestValues(TreeNode root) {
    ArrayList res = new ArrayList();
    LinkedList currLayer = new LinkedList<>();

    if(root != null) {
        currLayer.add(root);
    }

    while(currLayer.size() != 0) {
        int len = currLayer.size();
        int max = currLayer.peekFirst().val;

        for(int i = 0; i < len; i++) {
            TreeNode node = currLayer.removeFirst();
            if(node.left != null) {
                currLayer.add(node.left);
            }
            if(node.right != null) {
                currLayer.add(node.right);
            }
            if(max < node.val) {
                max = node.val;
            }
        }
        res.add(max);
    }
    return res;
}

116. 填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

public Node connect(Node root) {
    LinkedList currLayer = new LinkedList<>();

    if(root != null) {
        currLayer.add(root);
    }

    while(currLayer.size() != 0) {
        int len = currLayer.size();
        for(int i = 0; i < len; i++) {
            Node node = currLayer.removeFirst();
            if(node.left != null) {
                currLayer.add(node.left);
            }
            if(node.right != null) {
                currLayer.add(node.right);
            }
            if(i != len - 1) {
                node.next = currLayer.peekFirst();
            }
        }
    }
    return root;
}

也可以用递归的方法。

public Node connect(Node root) {
    if(root == null || root.left == null) {
        return root;
    }

    root.left.next = root.right;

    if(root.next != null) {
        root.right.next = root.next.left;
    }

    connect(root.left);
    connect(root.right);

    return root;
}

117. 填充每个节点的下一个右侧节点指针 II

给定一个二叉树。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

与上一题第一个层级遍历的代码相同。

翻转二叉树

226. 翻转二叉树

翻转一棵二叉树。

递归

public TreeNode invertTree(TreeNode root) {
    if(root == null) {
        return root;
    }

    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

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

    return root;
}

广度优先

使用FIFO队列层级遍历，每次遍历时翻转节点的左右子树。

深度优先

使用栈遍历，每次遍历时翻转节点的左右子树。

对称二叉树

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

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

// 比较tree1和tree2是否是对称的
private boolean symmetric(TreeNode tree1, TreeNode tree2) {
    if(tree1 == null && tree2 == null) {  // 都为null
        return true;
    }

    if(tree1 == null || tree2 == null) {  // 其中有一个为null
        return false;
    }
	
    // 比较根节点的值
    // 如果相同，则比较tree1的左子树与tree2的右子树，tree1的右子树与tree2的左子树
    return tree1.val == tree2.val && symmetric(tree1.left, tree2.right) && symmetric(tree1.right, tree2.left);
}

100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

与上一题类似的递归算法。

public boolean isSameTree(TreeNode p, TreeNode q) {
    if(p == null && q == null) {
        return true;
    }
    if(p == null || q == null) {
        return false;
    }

    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

572. 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if(isSameTree(root, subRoot)) {
        return true;
    }
    
    if(root == null) {
        return false;
    }
	
    // 左子树和右子树之间有一个存在该子树即可
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

// 判断tree1与tree2是否相等
private boolean isSameTree(TreeNode tree1, TreeNode tree2) {
    if(tree1 == null && tree2 == null) {
        return true;
    }
    if(tree1 == null || tree2 == null) {
        return false;
    }
    return tree1.val == tree2.val && isSameTree(tree1.left, tree2.left) && isSameTree(tree1.right, tree2.right);
}

二叉树的深度

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

使用递归方法，也可以用队列层级遍历。

public int maxDepth(TreeNode root) {
    return depth(root, 0);
}

private int depth(TreeNode root, int deep) {
    if(root == null) {
        return deep;
    }
    else {
        return Math.max(depth(root.left, deep + 1), depth(root.right, deep + 1));
    }
}

559. N 叉树的最大深度

给定一个 N 叉树，找到其最大深度。

递归方法：

public int maxDepth(Node root) {
    if(root == null) {
        return 0;
    }
    
    // 最大深度等于所有儿子节点中的最大深度+1
    int max = 0;
    for(Node child: root.children) {
        int depth = maxDepth(child);
        if(depth > max) {
            max = depth;
        }
    }
    return max + 1; 
}

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

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

递归

public int minDepth(TreeNode root) {
    if(root == null) {
        return 0;
    }

    if(root.left == null && root.right == null) {
        return 1;
    }
	
    // 左右子树都不为null，则最小深度位较小子树深度+1
    if(root.left != null && root.right != null) {
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
	
    // 左右子树有一个为null，则最小深度为不为空子树的深度+1
    if(root.left == null) {
        return minDepth(root.right) + 1;
    }
    else {
        return minDepth(root.left) + 1;
    }
}

一种更简洁的写法：

public int minDepth(TreeNode root) {
    if(root == null) {
        return 0;
    }

    int left = minDepth(root.left);
    int right = minDepth(root.right);

    if(left == 0 || right == 0) {
        return left + right + 1;
    }
    else {
        return Math.min(left, right) + 1;
    }
}

迭代

使用队列层级遍历，当遇到第一个叶子节点时返回。

public int minDepth(TreeNode root) {
    if(root == null) {
        return 0;
    }

    LinkedList currLayer = new LinkedList<>();
    currLayer.add(root);

    int depth = 0;
    while(currLayer.size() != 0) {
        depth++;
        int len = currLayer.size();
        for(int i = 0; i < len; i++) {
            TreeNode node = currLayer.removeFirst();
            if(node.left == null && node.right == null) {  // 遇到叶子节点
                currLayer.clear();  // 触发while循环终止条件
                break;
            }
            if(node.left != null) currLayer.add(node.left);
            if(node.right != null) currLayer.add(node.right);
        }
    }

    return depth;
}

完全二叉树节点个数

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

递归

节点个数=左子树个数+右子树个数+1。

public int countNodes(TreeNode root) {
    if(root == null) return 0;

    int left = countNodes(root.left);
    int right = countNodes(root.right);
    return left + right + 1;
}

迭代

可以继续用层级遍历的方法，但是效率太低(4ms)。可以先计算二叉树的深度(一直搜索最左边的节点)，然后计算最后一层节点的个数，因为除了最后一层， 之前层都是满节点的，这样效率更高(0ms)。

public int countNodes(TreeNode root) {
    if(root == null) return 0;
    int depth = 1;
    TreeNode node = root;
    while(node.left != null) {  // 计算深度
        depth++;
        node = node.left;
    }

    ArrayList list = new ArrayList<>();
    lastLayer(list, root, depth);
	
    // 除了最后一层的节点数量+最后一层节点数量
    return (int) Math.pow(2, depth - 1) - 1 + list.size();
}

// 将最后一层节点加入list
private void lastLayer(ArrayList list, TreeNode root, int depth) {
    if(root == null) return;

    if(depth == 1) {
        list.add(root);
    }
    else {
        lastLayer(list, root.left, depth-1);
        lastLayer(list, root.right, depth-1);
    }
}

平衡二叉树

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

自顶向下递归

如果一个二叉树左子树和右子树的高度差不大于1，且左子树、右子树都是是平衡的，则这个二叉树是平衡的。这种做法效率较低，因为节点的高度被重复计算了很多次。

// 左子树、右子树高度差<=1，且左子树、右子树都是平衡的
public boolean isBalanced(TreeNode root) {
    if(root == null) return true;
    int left = getHeight(root.left);
    int right = getHeight(root.right);
    return Math.abs(left-right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

// 左子树和右子树较大的高度+1
private int getHeight(TreeNode root) {
    if(root == null) return 0;
    int left = getHeight(root.left);
    int right = getHeight(root.right);
    return Math.max(left, right) + 1;
}

递归优化

对上面的算法做一些剪枝操作，避免重复计算，使用-1标记当前子树已经不平衡了，如果不平衡，则没有必要进行计算高度了。

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

private int getHeight(TreeNode root) {
    if(root == null) return 0;
	
    // 左子树或右子树已经不平衡了，那么当前树也不平衡
    int left = getHeight(root.left);
    if(left == -1) return -1;
    int right = getHeight(root.right);
    if(right == -1) return -1;
	
    if(Math.abs(left - right) > 1) return -1;  // 左子树、右子树高度差超过1，当前树不平衡
    return Math.max(left, right) + 1;  // 如果是平衡的，返回高度
}

二叉树的所有路径

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。

递归

public List binaryTreePaths(TreeNode root) {
    ArrayList list = new ArrayList<>();
    getPath(root, list, "");
    return list;
}

private void getPath(TreeNode root, List list, String path) {
    if(root == null) return;

    // 将当前节点添加到路径中
    path += root.val;

    if(root.left == null && root.right == null) {  // 走到叶子节点返回
        list.add(path);
    }
    else {  // 继续往左右子树探索
        path += "->";
        getPath(root.left, list, path);
        getPath(root.right, list, path);
    }
}

优化，使用可变字符串StringBuilder，此时要注意需要深拷贝。

public List binaryTreePaths(TreeNode root) {
    ArrayList list = new ArrayList<>();
    getPath(root, list, new StringBuilder(""));
    return list;
}

private void getPath(TreeNode root, List list, StringBuilder path) {
    if(root == null) return;

    path.append(root.val);

    if(root.left == null && root.right == null) {
        list.add(path.toString());
    }
    else {
        path.append("->");
        getPath(root.left, list, new StringBuilder(path.toString()));
        getPath(root.right, list, new StringBuilder(path.toString()));
    }
}