二叉树刷题总结：二叉树的属性

HelloWorld杰少

发布于 2022-08-04 14:22:45

5180

文章被收录于专栏：HelloWorld杰少HelloWorld杰少

是否对称

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

image

上图为对称二叉树

image

上图的二叉树则不是镜像的

思路

判断是否是镜像，需要去判断二叉树的里侧和外侧是否相同。

这就需要去判断根节点下左子树与右子树里侧和外侧是否相等。比较的方法是拿左子树的 “左-右-中” 节点和右子树的“右-左-中”为顺序的节点做比较。

这题用递归的方式解比较方便，递归的思路如下：

因为要比较俩个子树是否是镜像的，所以递归的参数为俩个，分别是左子树节点和右子树节点
终止条件有三个：

左节点为空，右节点不为空，返回 false，左节点不为空，右节点为空，返回 false；
左右节点均不为空，但数值不同，返回 false；
如果左右节点均为空，则返回 true；

如果以上条件均不满足，则再进入递归逻辑

代码实现

public boolean isSymmetric1(TreeNode root) {
        return compare(root.left, root.right);
    }

    private boolean compare(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;
        }
        // 比较外侧
        boolean compareOutside = compare(left.left, right.right);
        // 比较内侧
        boolean compareInside = compare(left.right, right.left);
        return compareOutside && compareInside;
    }

时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。

空间复杂度：O(H)，其中 H 是树的高度

二叉树的最大深度

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

思路

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

我们可以通过递归的方式求解此题：

递归函数的传入的参数为二叉树的根节点，返回值为二叉树的高度；
递归的终止条件为当节点为空节点时，返回高度为 0；
先求出它左子树的高度，然后再求出它右子树的高度，俩高度的最大值+1为二叉树的最大深度。

代码如下：

class solution {
public:
    int getdepth(treenode node) {
        if (node == null) return 0;
        int leftdepth = getdepth(node.left);       // 左
        int rightdepth = getdepth(node.right);     // 右
        int depth = 1 + Math.max(leftdepth, rightdepth); // 中
        return depth;
    }
    int maxdepth(treenode root) {
        return getdepth(root);
    }
};

时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。

空间复杂度：O(H)，其中 H 是树的高度

同理，该方法适用于求 N 叉树的最大深度，代码如下：

// 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;
    } else if (root.children.isEmpty()) {
      return 1;  
    } else {
      List<Integer> heights = new LinkedList<>();
      // 循环求出每个子树的高度
      for (Node item : root.children) {
        heights.add(maxDepth(item)); 
      }
      return Collections.max(heights) + 1;
    }
  }
}

时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。

空间复杂度：O(H)，其中 H 是树的高度

二叉树的最小深度

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

这里有个误区需要解释一下，是从根节点到最近的叶子节点，如果根节点没有左子树或者右子树，很多人就觉得最小深度为 1，这是不对的。是从根节点到最近叶子节点的最短路径上的节点数量才是最小深度。

可以看出, 求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

代码如下：

class Solution {
    /**
     * 递归法，相比求MaxDepth要复杂点
     * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null) {
            return rightDepth + 1;
        }
        if (root.right == null) {
            return leftDepth + 1;
        }
        // 左右结点都不为null
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。

空间复杂度：O(H)，其中 H 是树的高度。

求二叉树有多少个节点

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

此题可用求二叉树的最大深度的方式来求出，代码如下：

class solution {
public:
    int getdepth(treenode node) {
        if (node == null) return 0;
        int leftdepth = getdepth(node.left);       // 左
        int rightdepth = getdepth(node.right);     // 右
        int depth = 1 + leftdepth, rightdepth; // 中
        return depth;
    }
    int maxdepth(treenode root) {
        return getdepth(root);
    }
};

时间复杂度：O(n)，n 为二叉树节点个数空间复杂度：O(h)，h 为树的高度

平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

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

思路

既然是要求比较高度，则我们可以用到后序遍历的方式。

明确递归函数的参数和返回值，参数为传入的根节点，如果左右子树的返回值 > 1,则我们返回 -1，表示已经不是平衡二叉树了；
递归的终止条件为遇到了空节点，则 return 0, 表示当前节点为根节点，高度为 0；
单层递归逻辑为，分别求出左右子树的高度，如果差值小于等于 1，则返回当前二叉树的高度，否则返回 -1，表示已经不是二叉树了；

代码如下：

class Solution {
   /**
     * 递归法
     */
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private 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;
        }
        // 左右子树高度差大于1，return -1表示已经不是平衡树了
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

二叉树的所有路劲

给定一个二叉树，返回所有从根节点到叶子节点的路径。

思路

根据题意要从根节点到叶子节点的路径，所以需要前序遍历。

确定递归的参数和返回值，参数为传入的根节点，记录每条路径的节点值数组path，以及路径结果数组res；
当遇到叶子节点的时候终止，并将路径节点值数组里的数值转换成字符串，然后加入到结果数组；
递归的单层逻辑为，因为是前序遍历：中-左-右，所以先处理中间节点，加入到 path 中，然后再递归处理左子树和右子树，并递归完后回溯；

代码如下：

//解法一
class Solution {
    /**
     * 递归法
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<Integer> paths = new ArrayList<>();
        traversal(root, paths, res);
        return res;
    }

    private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
        paths.add(root.val);
        // 叶子结点
        if (root.left == null && root.right == null) {
            // 输出
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < paths.size() - 1; i++) {
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));
            res.add(sb.toString());
            return;
        }
        if (root.left != null) {
            traversal(root.left, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
        if (root.right != null) {
            traversal(root.right, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
    }
}

左叶子之和

计算给定二叉树的所有左叶子之和。

思路

首先要判断这棵二叉树有没有左叶子，就必须要通过节点的父节点来判断其左孩子是不是左叶子，判断代码如下：

 if (root.left != null && root.left.left == null && root.left.right == null) { // 中
            midValue = root.left.val;
        }

用后序遍历找出所有的左叶子节点数值之和，递归方式如下：

递归函数的传参为根节点，返回值为左叶子节点之和；
递归终止条件为 root == null 返回 0；
单层递归逻辑：当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和；

代码如下：

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int leftValue = sumOfLeftLeaves(root.left);    // 左
        int rightValue = sumOfLeftLeaves(root.right);  // 右
                                                       
        int midValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) { // 中
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;
        return sum;
    }
}

左下角的值

给定一个二叉树，在树的最后一行找到最左边的值。

思路

本题比较容易下手的解题方式可以用层序遍历的方法，找到最后一行的最左边。

但是也可以用递归法来实现，首先可以明确深度最大的叶子节点一定是最后一行，那如何找最左边的呢？我们可以使用前序遍历，优先从左边开始搜索。

明确递归函数的参数和返回值：参数为传入的根节点，以及一个int型变量用来记录最长深度。返回值为 void；
当遇到叶子节点的时候，为终止条件，并开始统计最大深度；
确定单层递归逻辑，当不是叶子节点时，则继续遍历左子树和右子树，并记得要回溯；

代码如下：

// 递归法
class Solution {
    private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,0);
        return value;
    }

    private void findLeftValue (TreeNode root,int deep) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        if (root.left != null) findLeftValue(root.left,deep + 1);
        if (root.right != null) findLeftValue(root.right,deep + 1);
    }
}

路劲总和 1

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

思路

利用递归来解答此题：

确定递归函数的传参和返回值：参数为传入的根节点和计数变量，该计数变量每次递归的时候需要减去当前节点的值，最后遇到叶子节点的时候判断该叶子节点的值是否与它一致，如果一致，则表示找到了该路径。返回值为bool类型；
递归函数的终止条件为：当遇到叶子节点的时候，并且计数变量等于叶子节点的值就返回 true;
单层递归逻辑为：遍历左子树和右子树，并回溯

代码如下：

class solution {
   public boolean haspathsum(treenode root, int targetsum) {
        if (root == null) {
            return false;
        }
        targetsum -= root.val;
        // 叶子结点
        if (root.left == null && root.right == null) {
            return targetsum == 0;
        }
        if (root.left != null) {
            boolean left = haspathsum(root.left, targetsum);
            if (left) {// 已经找到
                return true;
            }
        }
        if (root.right != null) {
            boolean right = haspathsum(root.right, targetsum);
            if (right) {// 已经找到
                return true;
            }
        }
        return false;
    }
}

// 精简后的代码

class solution {
    public boolean haspathsum(treenode root, int targetsum) {
        
        if (root == null) return false; // 为空退出
        
        // 叶子节点判断是否符合
        if (root.left == null && root.right == null) return root.val == targetsum;

        // 求两侧分支的路径和
        return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
    }
}

路径总和2

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

思路

解题思路与上一题相似，只是需要记录路径。

代码如下：

class solution {
    public list<list<integer>> pathsum(treenode root, int targetsum) {
        list<list<integer>> res = new arraylist<>();
        if (root == null) return res; // 非空判断
        
        list<integer> path = new linkedlist<>();
        preorderdfs(root, targetsum, res, path);
        return res;
    }

    public void preorderdfs(treenode root, int targetsum, list<list<integer>> res, list<integer> path) {
        path.add(root.val);
        // 遇到了叶子节点
        if (root.left == null && root.right == null) {
            // 找到了和为 targetsum 的路径
            if (targetsum - root.val == 0) {
                res.add(new arraylist<>(path));
            }
            return; // 如果和不为 targetsum，返回
        }

        if (root.left != null) {
            preorderdfs(root.left, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
        if (root.right != null) {
            preorderdfs(root.right, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

最后

好了，关于二叉树属性的总结到这里就结束了。相信看完这篇文章，你会对二叉树属性有一定的了解，感谢你的阅读。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-11-08，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自 HelloWorld杰少微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

登录后参与评论

0 条评论

热度