当前位置：首页 > article >正文

代码随想录算法训练营| 110.平衡二叉树、 257. 二叉树的所有路径、404.左叶子之和、 222.完全二叉树的节点个数

article 2024/11/18 22:47:54

110.平衡二叉树

题目

参考文章

思路：这道题其实求的就是高度，所以我们用类似后序遍历的方法进行。首先查看左右子树的高度，如果左右子树的高度为-1 （这个-1是用于表示高度差大于1的情况），则返回-1

如果左右子树高度不为-1，则判断leftHeight和rightHeight的高度差是否大于1，如果大于1，则返回-1；否则就返回leftHeight和rightHeight的最大值+1；这样就可以找到高度差了，只要不等于-1，就是平衡二叉树

代码：

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -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(leftHeight - rightHeight) > 1){
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

257. 二叉树的所有路径

题目

参考文章

思路：这里用到了前序遍历和回溯算法，设定一个存储路径的数组res和一个存储遍历二叉树中存储二叉树数值的数组paths。然后先把当前元素值添加到paths中，判断当前节点左右子树是否为空，为空，则表示遇到了叶子节点，则把当前的paths数组中的所有的元素放到res中，存储成为一个路径，如果没有遇到叶子节点，则继续遍历，若左节点不为空，则继续遍历左节点，遍历完成就回溯到上一个节点（在paths中），若右节点不为空，则遍历右节点，遍历完成就回溯到上一个节点（在paths中）

代码：

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);// 回溯
        }
    }
}

404.左叶子之和

题目

参考文章

思路：这题求左叶子的和，用后序遍历的方式最合适，因为就是相当于找到了当前节点左右子树对应的左叶子节点值的和，然后返回给当前节点，再一层层往父节点返回。所以先寻找左右子树的左叶子节点值的和，然后当找到当前节点的左子树不为空，且左子树左右子树都为空，表示当前节点的左子树就是左叶子节点，记录该值即可；最后返回他们的和即可。sum其实就是相当于返回给父节点的左右子树的左叶子节点值的和。

代码：

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;
    }
}

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

题目

参考文章

思路：题目中的是完全二叉树，所以我们可以用完全二叉树的特性，在某种情况下，其子树有可能出现满二叉树的情况，所以我们当遇到要给满二叉树时，我们可以直接用满二叉树的公式来返回节点数即可（2^满二叉树高度-1），其他情况则遍历左右子树，统计个数即可。

代码：

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth=0;
        int rightDepth=0;
        //左子树深度
        while(left!=null){
            left=left.left;
            leftDepth++;
        }
        //右子树深度
        while(right!=null){
            right=right.right;
            rightDepth++;
        }
        
        if(leftDepth==rightDepth){
            return (2 << leftDepth) - 1; //利用满二叉树的特点，返回节点个数
        }

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

查看全文

http://www.kler.cn/a/322754.html