Leetcode – 探索 – 树篇 – 基础

发布于 20 天前  10 次阅读 本文共4250个字


时隔多少年,再次开启刷题之路

树的遍历

二叉树的前序遍历

给定一个二叉树,返回它的 前序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

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

public class Solution {

    private List<Integer> result = new ArrayList<>();

    // 二叉树的前序遍历  - 中 左  右
    public List<Integer> preorderTraversal(TreeNode root) {
        preorder(root);
        return result;
    }

    private void preorder(TreeNode root){
        if (root == null)
            return ;
        result.add(root.val);
        preorder(root.left);
        preorder(root.right);
    }

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗:37.8 MB, 在所有 Java 提交中击败了73.83%的用户

二叉树的中序遍历

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

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

public class Solution {

    private List<Integer> result = new ArrayList<>();

    // 二叉树的中序遍历  - 中 左  右
    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root);
        return result;
    }

    private void inorder(TreeNode root){
        if (root == null)
            return ;
        inorder(root.left);
        result.add(root.val);
        inorder(root.right);
    }
}

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗:37.7 MB, 在所有 Java 提交中击败了94.06%的用户

二叉树的后序遍历

给定一个二叉树,返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

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

public class Solution {

    private List<Integer> result = new ArrayList<>();

    // 二叉树的中序遍历  - 中 左  右
    public List<Integer> postorderTraversal(TreeNode root) {
        postorder(root);
        return result;
    }

    private void postorder(TreeNode root){
        if (root == null)
            return ;
        postorder(root.left);
        postorder(root.right);
        result.add(root.val);
    }
}

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗:37.7 MB, 在所有 Java 提交中击败了91.22%的用户

二叉树的层次遍历

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

示例:

二叉树:[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

[
  [3],
  [9,20],
  [15,7]
]
import java.util.ArrayList;
import java.util.List;

public class Solution { 
    private List<List<Integer>> trees = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)
            return trees;
        // 添加第一个
        levelOrderHelp(root, 0);
        return trees;
    }

    private void levelOrderHelp(TreeNode root, int level){
        if (root == null)
            return ;
        // add
        if(trees.size() == level)
            trees.add(new ArrayList<>());
        // ==
        trees.get(level).add(root.val);

        // 下一层
        levelOrderHelp(root.left, level +1);
        levelOrderHelp(root.right, level + 1);
    }

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗:39.9 MB, 在所有 Java 提交中击败了69.40%的用户

运用递归解决问题

二叉树的最大深度 - 自下向上

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

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

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

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗:39.8 MB, 在所有 Java 提交中击败了41.67%的用户

二叉树的最大深度 - 自顶向下

private int max_depth = 0;
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        maximun_depth(root, 1);
        return  max_depth;
    }

    private void maximun_depth(TreeNode root, int depth){
        if (root == null)
            return;

        if (root.left == null && root.right == null)
            max_depth = Math.max(max_depth, depth);

        maximun_depth(root.left, depth + 1);
        maximun_depth(root.right, depth + 1);
    }

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗:40 MB, 在所有 Java 提交中击败了9.96%的用户

对称二叉树

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

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

进阶:

你可以运用递归和迭代两种方法解决这个问题吗?

    private boolean mirror(TreeNode left, TreeNode right)
    {
        if (left == null && right != null)
            return false;
        if (left != null && right == null)
            return false;
        if (left == null && right == null)
            return true;
        if (left.val != right.val)
            return false;

        return mirror(left.left, right.right) && mirror(left.right, right.left);
    }
    // 镜像二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null || (root.left == null && root.right == null) )
            return true;

        return mirror(root.left, root.right);
    }

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗:38.2 MB, 在所有 Java 提交中击败了23.35%的用户

路径总和

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树,以及目标和 sum = 22

```
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
```

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2

 // 路径和
    public boolean hasPathSum(TreeNode root, int sum) {
        // 如果根结点就
        if (root == null)
            return false;
        if (root.left == null && root.right == null)
        {
            if (root.val != sum)
                return false;
            else
                return true;
        }
        return hasPathSum_Help(root.left, root.val, sum) || hasPathSum_Help(root.right, root.val, sum);
    }

    // 辅助函数
    private boolean hasPathSum_Help(TreeNode root, int length, int sum)
    {
        if (root == null)
            return false;
        if (root.left == null && root.right == null)
        {
            if (length + root.val == sum)
                return true;
            else
                return false;
        }
        return hasPathSum_Help(root.left, root.val + length, sum) || hasPathSum_Help(root.right, root.val +length, sum);
    }

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗:39.9 MB, 在所有 Java 提交中击败了20.25%的用户


粉色的花瓣,美丽地缠绕在身上。依在风里。