二叉树题目合集-阿里云开发者社区

求二叉树是否相同？

用递归法，传入左右两棵树的根节点，然后比较 left.left == right.left; 以及 left.right ==right.right;

这是递归里面的内容

递归结束的条件：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if( p == null && q == null){
         return true ; // 这样的情况下就可以返回true了
        }else if ( p != null && q == null){
            return false;
        }else if( p == null && q != null ){
            return false;
        }else if (p.val != q.val){
            return false;
        }else{
            //递归的内容
            boolean b1 = isSameTree(p.left , q.left);
            boolean b2 = isSameTree(p.right ,q.right);
            boolean b = b1 && b2;
            return b;
        }  
    }
}

求二叉树是否对称？

class Solution {
    //这里我们用队列来实现，思路： 
        //将左右子树分开，然后分别以左右为树比较
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }else{
            return isTrue(root.left , root.right);
        }
    }
    public boolean isTrue(TreeNode left, TreeNode right){
        if(left == null && right == null){
            return true;
        }else if(left == null || right == null){
            return false;
        }else if(left.val != right.val ){
            return false;
        }
        else{
            return isTrue(left.left,right.right) && isTrue(left.right , right.left);
        }
    }
}

求完全二叉树的节点数

方法一：最原始的方法，用迭代法或者递归的方法将二叉树遍历完，得出节点的数量

方法二：只针对完全二叉树的解法

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

按照这个完全二叉树的特征。我们就可以确定一个终止条件

if(leftDepth == rightDepth){
  return 2<<leftDepth - 1;
}

完全二叉树只有两种情况

情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

所以说如果整棵树不是满二叉树的话，那么就递归他的左右孩子，直到递归到某棵子树，它（子树）是满二叉树，那么就达到递归截至的条件，输出节点数。

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        TreeNode leftD = root.left;
        TreeNode rightD = root.right;
        int rD = 0;
        int lD = 0;//初始化为0 是为了后面求指数方便
      //求左右子树的深度
        while(leftD != null){
            leftD = leftD.left;
            lD++;
        }
        while(rightD != null){
            rightD = rightD.right;
            rD++;
        }
      //如果判断该树是满二叉树那么直接输出即可
        if(rD == lD){
            return (2 << lD) - 1; // 2^n - 1
        }
      //继续递归，计算完左右子树的节点，然后再加上根节点;
        lNum = countNodes(root.left);
        rNum =  countNodes(root.right);
        return lNum + rNum + 1;
    }
}

总结：对于这个二叉树来说，他没有遍历所有的节点，如果说一个节点的子树他是满二叉树，那么就只需要用2 << n - 1这个公式就能算出这个子树的所有节点。

平衡二叉树

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

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

求解高度用后序遍历，求解深度用前序遍历

【因为后序是根据左右孩子的高度，然后父节点再根据左右孩子节点的情况进行 + 1 ===》》》层层向上返回】

【前序求解的深度，顺序是 [中左右]一直向下遍历，不向上返回结果。符合一直向下统计节点的深度】

class Solution {
    public boolean isBalanced(TreeNode root) {
        int res = isTree(root);
        return res == -1 ? false : true;
    }
    //先定义一个方法判断平衡二叉树
    public int isTree(TreeNode node){
        if(node == null){
            return 0;
        }
        int ll = isTree(node.left);
        if(ll == -1){
            return -1;
        }
        int rl = isTree(node.right);
        if(rl == -1){
            return -1;
        }
        //判断是否满足平衡二叉树的条件
        if(Math.abs(ll-rl) > 1){
            return -1;
        }
        //返回平衡二叉树的高度
        return Math.max(ll,rl) + 1;
    }
}

求解深度的方法(c++ 实现)

class Solution {
public:
    int result;
    void getDepth(TreeNode* node, int depth) {
        result = depth > result ? depth : result; // 中
        if (node->left == NULL && node->right == NULL) return ;
        if (node->left) { // 左
            depth++;    // 深度+1
            getDepth(node->left, depth);
            depth--;    // 回溯，深度-1
        }
        if (node->right) { // 右
            depth++;    // 深度+1
            getDepth(node->right, depth);
            depth--;    // 回溯，深度-1
        }
        return ;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == 0) return result;
        getDepth(root, 1);
        return result;
    }
};

二叉树的所有路径

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

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

求二叉树的所有路径思路（草图）

创建路径集合path 以及结果集合list。用于存储路径与最后的结果
前序遍历，先将父节点加入到路径集合path中
递归结束的条件 –> 到叶子节点（如图的 4 号节点）
递归结束，回溯之前。将该路径保存到结果路径中

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        //用递归 ，前序遍历
        List<String> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        List<Integer> path = new ArrayList<>(); 
        prefix(root,path,list);
        return list;
    }
    public void prefix(TreeNode node , List<Integer> path, List<String> list){
      //先将该节点保存到路径
        path.add(node.val);
        //如果到叶子节点就结束本次递归
        if(node.left == null && node.right == null){
            //StringBuffer用于拼接路径
            StringBuffer sb = new StringBuffer();
            //循环拼接路径
            for(int i=0 ;i<path.size() - 1 ;i++){
                //因为当前的节点都已经保存到了path中，所以这里只需要循环按要求拼接即可
                sb.append(path.get(i)).append("->");
            }
            /*
        因为最后循环结束时如果我们将最后一个节点也拼接进入 ，那么势必会多出来一个‘->’这就与题目要求的不符合
      所以我们将最后一个节点放到循环外面拼接
            */
            sb.append(path.get(path.size()-1)); 
            //将拼接好的路径保存起来
            list.add(sb.toString());
           // 结束本次递归
            return;
        }
        if(node.left != null){
            prefix(node.left , path ,list);
            //递归结束 ，回溯时删除最后一个节点，【1-> 2 -> 5】路径就会变成【1 -> 2 -> 】
          //这样下次递归就会从【2】节点开始 
            path.remove(path.size() - 1 );
        }
        if(node.right != null){
            prefix(node.right , path , list);
            path.remove(path.size() - 1);
        }
    }
}

获取树最左下角的节点的值

//方法一 ； 递归法
class Solution {
    public int res = 0;
    public int depth =  - 1;
    public int findBottomLeftValue(TreeNode root) {
        if(root == null){
            return 0;
        }
        GetLeft(root,1);
        return res;  
    }
    public void GetLeft(TreeNode root , int deep){
        if(root.left == null && root.right == null){
            if(deep > depth){
                depth = deep;
                res = root.val;
            }  
        }
        if(root.left != null){
            GetLeft(root.left , deep+1);
        }
        if(root.right != null){
            GetLeft(root.right, deep + 1);
        }
    }
}
//方法二 ： 迭代法
 */
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public int findBottomLeftValue(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int size = que.size();
            List<Integer> nodeList = new ArrayList<>();
            for(int i= 0 ;i<size;i++){
                TreeNode node = que.poll();
                nodeList.add(node.val);
                if(node.left != null){
                    que.offer(node.left);
                }
                if(node.right != null){
                    que.offer(node.right);
                }
            }
            list.add(nodeList);
        }
        return list.get(list.size()- 1).get(0);
    }
}
//迭代法二 ： 
//迭代法
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (i == 0) {
                    res = poll.val;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return res;
    }
}

路径总和二

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

叶子节点是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5

输出：[]

示例 3：

输入：root = [1,2], targetSum = 0

输出：[]

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root== null){
            return list;
        }
        List<Integer> path = new ArrayList<>();
         prefix(root,path,targetSum);
        return list;
    }
    public void prefix(TreeNode root, List<Integer> path,int targetSum){
        path.add(root.val);
        if(root.left == null && root.right == null){
            List<Integer> alist= new ArrayList<>();
            for(int i= 0;i<path.size();i++){
                alist.add(path.get(i));
            }
            int size = alist.size();
            int sum = 0;
            for(int j =0;j<size;j++){
                sum += alist.get(j);
            }
            if(sum == targetSum){
                list.add(alist);
            }
        }
        if(root.left != null){
            prefix(root.left , path, targetSum);
            path.remove(path.size()-1);
        }
        if(root.right != null){
            prefix(root.right , path, targetSum);
            path.remove(path.size()-1);
        }
    }
}

从中序与后序构建二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]输出：[3,9,20,null,null,15,7]示例 2:

输入：inorder = [-1], postorder = [-1]输出：[-1]

思路

判断数组是否为空！
不为空则向下继续，为空返回null
去后序数组中的最后一个元素为树的头节点的val值，（原因由后序遍历可知）
切割中序数组，以头节点的val值为区分（作为切割点），切割成中序左数组和中序右数组
切割后序数组，切成后序左数组和后序右数组
递归处理左右区间

思维图

代码实现（复杂易懂）

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length == 0 || postorder.length == 0){
            return null;
        }
        int rootVal = postorder[postorder.length - 1];
        TreeNode node = new TreeNode(rootVal);
        int inSize = inorder.length;
        int postSize = postorder.length;
        int mid; 
        for(mid = 0; mid < inSize;mid++){
            if(inorder[mid] == rootVal){
                break;
            }
        }
        //切割中序
        int inBegin =  0;
        int inEnd = mid;
        int[] newIn = Arrays.copyOfRange(inorder,inBegin,inEnd);
        int[] newPost = Arrays.copyOfRange(postorder,inBegin,inEnd);
        node.left = buildTree(newIn,newPost);
        int postBegin = mid + 1 ;
        int postEnd = postorder.length - 1;
        int[] newIn2 = Arrays.copyOfRange(inorder , postBegin , inSize);
        int[] newPost2 = Arrays.copyOfRange(postorder,mid, postEnd);
        node.right = buildTree(newIn2,newPost2);
        return node;
    }
}

代码实现（简易map版）

class Solution {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);
        return root;
    }
}

从前序与中序构建二叉树

思路

与从中序和后序构建二叉树相同

代码实现

class Solution {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);
        return root;
    }
}

参考说明（感谢！）：

力扣！

代码随想录！

二叉树题目合集

求二叉树是否相同？

求二叉树是否对称？

求完全二叉树的节点数

平衡二叉树

二叉树的所有路径

求二叉树的所有路径思路（草图）

获取树最左下角的节点的值

路径总和二

从中序与后序构建二叉树

从前序与中序构建二叉树

代码实现

参考说明（感谢！）：

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

二叉树题目合集

求二叉树是否相同？

求二叉树是否对称 ？

求完全二叉树的节点数

平衡二叉树

二叉树的所有路径

求二叉树的所有路径思路（草图）

获取树最左下角的节点的值

路径总和二

从中序与后序构建二叉树

从前序与中序构建二叉树

代码实现

参考说明（感谢！）：

热门文章

最新文章

相关电子书

求二叉树是否对称？