LeetCode刷题日记之二叉树的属性🧐🧐🧐

简介

本文为博主的LeetCode刷题日记，希望所记录的内容能够对大家有所启发，在撰写这部分内容的时候博主的《代码随想录》学习到了二叉树属性部分，在二轮学习的时候博主会将前序的知识点（数组、链表、栈与队列、字符串、哈希表）的内容重新整理，一起加油吧朋友们！💪💪💪

完全二叉树的节点个数

LeetCode题目链接

给一个完全二叉树的根节点root，求出该树的节点个数，完全二叉树实际上就是除了底层节点右部分没填满外，其他各层节点都为最大值。

首先我们用递归法来解决这道问题，递归法三要素：

• 确定递归函数的参数和返回值
• 确定递归出口
• 确定单层二叉树递归的逻辑

首先递归函数参数的话便是树的根节点，返回值就是树的节点数量

private int getTreeNums(TreeNode root){}

递归的出口便是当root为空时返回0表示节点数为0

if(root == null){return 0;}

在单层逻辑的处理上，先求左子树的节点数量，再求右子树的节点数量，最后加上根节点自己即可

return getTreeNums(root.left) + getTreeNums(root.right) + 1;

所以递归的代码如下：

/*递归法求完全二叉树节点个数*/
class Solution{
    public int countNodes(TreeNode root){
        return getTreeNums(root);
    }
    
    private int getTreeNums(TreeNode root){
        if(root == null){return 0;}
        return getTreeNums(root.left) + getTreeNums(root.right) + 1;
    }
}

递归法掌握后迭代法同样也得掌握，用队列结合层序遍历策略即可求出完全二叉树的节点个数

/*迭代法求完全二叉树节点个数*/
class Solution{
    public int countNodes(TreeNode root){
        if(root == null){return 0;} //提前结束
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int result = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode cur = queue.poll();
                result++;
                if(cur.left != null){queue.offer(cur.left);}
                if(cur.right != null){queue.offer(cur.right);}
            }
        }
        return result;
    }
}

除了上述两种常规方法外针对于完全二叉树自身的属性特性来说，还有另外一种方法🤔🤔🤔，因为满二叉树的节点数与其深度depth存在关系

nodeNums = 2 * depth - 1

然后完全二叉树的左子树和右子树本质上就是满二叉树，所以我们可以通过计算左右子树的深度来计算整个完全二叉树的节点数💡💡💡

• 递归的入参为树的根节点，返回值为完全二叉树的节点数

• 递归的出口为如果root为null则返回0，若不为null则根据左右子树的深度来判断该子树是不是满二叉树

• 递归的单层逻辑仍为左右子树的节点数总和加一

也就是说该迭代法与常规迭代法不同之处仅在于求节点数的方法不同🤔🤔🤔

class Solution {
    public int countNodes(TreeNode root){
        return getTreeNums(root);
    }
    
    private int getTreeNums(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 getTreeNums(root.left) + getTreeNums(root.right) + 1; //如果子树不是满二叉树则继续递归
    }
}

通过这三个方法，这道求完全二叉树的节点数的题目我们就彻底掌握了，若后续有遗忘再回来复习一下即可🐭🐭🐭

平衡二叉树

LeetCode题目链接

给定一个二叉树来判断其是否是平衡二叉树，而平衡二叉树就是左右子树的高度差的绝对值不超过1

这里我们要强调一个概念就是二叉树的深度和高度的概念🤔🤔🤔

• 二叉树节点的深度是指从根节点到该节点的路径边上的节点个数
• 二叉树节点的高度是指该节点到叶子节点的最长路径边的条数

简单来说就是往下是深度增加，往上是高度增加，深度和高度都是从1开始😮😮😮

我们来分析该题的递归三要素：

• 递归的入参为节点，返回值为该节点的高度但如果当前节点为根节点的二叉树不是平衡二叉树的话返回高度无意义，故若递归时判断出不为平衡二叉树则返回-1
• 递归的出口为遇到空节点则返回0，表示当前节点为根节点的树的高度为0
• 单层递归的逻辑即是分别求出左右子树的高度，然后差值小于1则返回当前二叉树高度否则返回-1

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

    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;}
        if(Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

掌握递归解法后我们来进一步掌握迭代解法🫡🫡🫡

求深度从上往下可以通过层序遍历来计算，但是高度是一个从下往上的定义值所以无法通过层序遍历来求高度🤔🤔🤔

所以我们可以通过借助栈的后序遍历来找每个节点的高度，因为是借助栈所以这里实际上还是通过求根节点的最大深度来求的高度😮😮😮，这里迭代法的效率比较低，博主就先不码了，后面有时间会补上🫡🫡🫡

二叉树的所有路径

LeetCode题目链接

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

因为要从根节点到叶子节点的路径所以需要前序遍历（中左右），而且该题需要把路径记录下来进行回溯，通过回溯来从一个路径回退再进入另一个路径🤔🤔🤔，ok，我们来梳理递归三要素吧

• 递归的入参和返回值：传入根节点，一个存放每一条路径的path和一个存放结果的result，因此不需要返回值。

private void traversal(TreeNode root, List<Integer> paths, List<String> result)

• 递归的出口：这里递归遇到叶子节点为终止，本题如果像一贯的if(cur == null){出口}这样的写法的话会导致本体的处理很麻烦，因为找到叶子节点就开始结束的处理逻辑（把路径放入result中）🤔🤔🤔

if(cur.left == null && cur.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));
	result.add(sb.toString());
	return;
}

• 单层的递归处理逻辑为先处理中间节点，将中间节点放进path中，然后判断中间节点是否是叶子节点，若不为空则递归处理左子节点和右子节点，当递归到叶子节点将path处理放到result中后要进行回溯处理，进行节点删除，那要怎么写呢？🤔🤔🤔其中有一点需要知道的是回溯和递归是一一对应的，回溯和递归要永远在一起，因为递归到叶子节点后进行回溯对吧😮😮😮

if(root.left != null){
	traversal(roor.left, paths, result)
	paths.remove(paths.size() - 1); //回溯
}
if(root.right != null){
	traversal(roor.right, paths, result)
	paths.remove(paths.size() - 1); //回溯
}

梳理完毕后我们来码递归的解决方法吧🫵🫵🫵

/**递归法 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        List<Integer> paths = new ArrayList<>();
        if(root == null){return result;} //提前终止
        traversal(root, paths, result);
        return result;
    }

    private void traversal(TreeNode root, List<Integer> paths, List<String> result){
        paths.add(root.val); 
        if(root.right == null && root.left == null){
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < paths.size() - 1; i++){
                sb.append(paths.get(i)).append("->"); //StringBuilder类型可以直接append整数
            }
            sb.append(paths.get(paths.size() - 1)); //最后不用添加"->"单独处理
            result.add(sb.toString());
            return;
        }
        //回溯递归同时进行
        if(root.left != null){
            traversal(root.left, paths, result);
            paths.remove(paths.size() - 1); //列表移除元素为remove
        }
        if(root.right != null){
            traversal(root.right, paths, result);
            paths.remove(paths.size() - 1);
        }

    }
}

处理完了递归的解法，当然就是要继续接着处理迭代的解法啦，迭代的话依赖使用前序遍历的迭代方式来处理，用一个栈来模拟递归，用另一个栈来存放对应的遍历路径💡💡💡

 /**迭代法 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if(root == null){return result;} //提前终止
        Stack<TreeNode> stack = new Stack<>(); 
        Stack<String> paths = new Stack<>();
        stack.push(root);
        paths.push(String.valueOf(root.val));
        while(!stack.isEmpty()){
            String path = paths.pop();
            TreeNode cur = stack.pop();
            //如果迭代到叶子节点
            if(cur.left == null && cur.right == null){
                result.add(path);
            }
            if(cur.left != null){
                stack.push(cur.left);
                paths.push(path + "->" + cur.left.val);
            }
            if(cur.right != null){
                stack.push(cur.right);
                paths.push(path + "->" + cur.right.val);
            }
        }
        return result;
    }

}

今天的LeetCode学习就到这里啦！！！改天见💤💤💤

本周小结

哈哈，博主隔天来总结二叉树属性的题目啦😁😁😁

首先是判断二叉树是否对称这一问题，嘻嘻博主后续会补上这一知识点的学习笔记🤫🤫🤫，这类题目的本质是要比较左右子树，遍历这两颗树来比较外侧和内侧的节点是否相同，也就是说左子树的遍历顺序是左右中那对应的右子树的遍历顺序就是右左中，这是递归的思路🫡🫡🫡

迭代的话就是要借助容器来成对的存放我们要比较的节点，这个容器可以是队列、栈甚至数组都可以🫡🫡🫡

梳理完直接开刷这一类题目👊👊👊

100. 相同的树 - 力扣（LeetCode）

572. 另一棵树的子树 - 力扣（LeetCode）

其中相同的树这道题目在对比二叉树是否对称的基础上来判断二叉树是否相同，在理清楚递归三要素后这道题就变得简单多了，拿捏🤏🤏🤏

 /**递归法 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return compare(p, q);
    }
    private boolean compare(TreeNode p, TreeNode q){
        //递归出口
        if(p == null && q == null){return true;}
        if(p != null && q == null){return false;}
        if(p == null && q != null){return false;}
        if(p.val != q.val){return false;}

        //单层处理逻辑
        boolean leftCompare = compare(p.left, q.left);
        boolean rightCompare = compare(p.right, q.right);
        boolean isSame = leftCompare && rightCompare;
        return isSame;
    }
}

/**迭代法 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //提前结束
        if(p == null && q == null){return true;}
        if(p == null || q == null){return false;}

        Deque<TreeNode> deque = new LinkedList<>();
        deque.addFirst(p);
        deque.addLast(q);
        while(!deque.isEmpty()){
            int size = deque.size() / 2;
            for(int i = 0; i < size; i++){
                TreeNode left = deque.pollFirst();
                TreeNode right = deque.pollLast();
                if(left == null && right == null){continue;} //还得接着判断
                if(left == null || right == null || (left.val != right.val)){ //这里注意先判空再判值
                    return false;
                }

                //注意入队顺序
                deque.addFirst(left.left);
                deque.addFirst(left.right);
                deque.addLast(right.left);
                deque.addLast(right.right);

            }
        }
        return true;
    }
}

而另一颗树的子树这道题目是给到两棵树，判断一颗树中是否包含与另一颗树的相同结构和节点值的子树，处理逻辑几乎感觉和相同的树一样了，话不多说直接开码！

/**递归法 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return findSubtree(root, subRoot);
    }

    private boolean findSubtree(TreeNode root, TreeNode subRoot){
        //递归出口
        if(subRoot == null){return true;}
        if(root == null){return false;}
        //单层逻辑
        return findSubtree(root.left, subRoot) || findSubtree(root.right, subRoot) || isSame(root, subRoot);
    }

    /**嵌套递归判断两树是否相同 */
    private boolean isSame(TreeNode root, TreeNode subRoot){
        if(root == null && subRoot == null){return true;}
        if(root == null || subRoot == null || root.val != subRoot.val){return false;}
        return isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
    }
}

这里博主就偷下懒，迭代法就交给各位啦👍👍👍

除了判断对称、相同、是否子树外还学习了如何求二叉树的最大深度，可以用前序遍历或者后序遍历，前序遍历求的是深度，后序遍历就是求高度（但因为根节点的高度就是二叉树的最大深度）

/*递归法*/
class Solution {
    public int maxDepth(TreeNode root) {
        return getDepth(root);
    }
     private int getDepth(TreeNode root){ //确定递归的参数和返回值
        if(root == null){ //递归出口
            return 0;
        }
        //确认单层递归逻辑
         return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
     }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){return 0;}
        Deque<TreeNode> deque = new LinkedList<>(); //双端队列的声明要<>
        deque.offer(root);
        int depth = 0;
        while(!deque.isEmpty()){
            int levelSize = deque.size();
            depth++;
            for(int i = 0; i < levelSize; i++){
                TreeNode cur = deque.poll();
                if(cur.left != null){deque.offer(cur.left);}
                if(cur.right != null){deque.offer(cur.right);}
            }
        }
        return depth;
    }
}

掌握了求最大深度后可以顺便把下面的题给刷掉，这里的迭代解法博主再偷一下下懒，交给各位啦😎😎😎

559. N 叉树的最大深度 - 力扣（LeetCode） 👈👈👈

/**递归法 */
class Solution {
    public int maxDepth(Node root) {
        return getDepth(root);
    }
    private int getDepth(Node root){
        //递归出口
        if(root == null){
            return 0;
        }
        //确定单层逻辑
        int max = 0; //比较多个子树的最大深度
        int temp = 0; //减少重复计算
        for(int i = 0; i < root.children.size(); i++){
            if(i == 0){max = getDepth(root.children.get(0));}
            else{
                temp = getDepth(root.children.get(i));
                max = temp > max ? temp : max;
            }
        }
        return max + 1;
    }
}

除了求最大深度外还学习了求最小深度，这里大家需要注意的是最小深度是从根节点到最近叶子节点的最短路径上的节点数量，而这里的叶子节点是指左右子节点都为空的节点，也就是说递归的出口不要指到叶子节点的左右空孩子上去，指到叶子节点即可🤔🤔🤔

/**递归法 */
class Solution {
    public int minDepth(TreeNode root) {
        return getMinDepth(root);
    }
    private int getMinDepth(TreeNode root){
        if(root == null){return 0;}

        if(root.left == null && root.right != null){
            return 1 + getMinDepth(root.right);
        }
        if(root.left != null && root.right == null){
            return 1 + getMinDepth(root.left);
        }
        return 1 + Math.min(getMinDepth(root.left), getMinDepth(root.right));

    }
}

/**迭代法（层序遍历） */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){return 0;}

        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while(!deque.isEmpty()){
            int size = deque.size();
            depth++;
            for(int i = 0; i < size; i++){
                TreeNode cur = deque.poll();
                if(cur.left == null && cur.right == null){return depth;}
                if(cur.left != null){deque.offer(cur.left);}
                if(cur.right != null){deque.offer(cur.right);}
            }
        }
        return depth;
    }
    
}

并且还学习了怎么求二叉树的节点数量，上面有相关内容，这里博主就不多赘述啦，在判断二叉树是否是平衡二叉树时，这里的话就是总结一下一般前中后序遍历的时候迭代方法借助栈，如果是层序遍历就用队列，当然并不绝对。另外对于二叉树的高度和深度要梳理清楚，一个是从上往下，一个是从下往上。🤔🤔🤔

在找二叉树所有路径的学习时，我们要清楚回溯和递归是伴生存在的，这点要注意。🤔🤔🤔

好啦，今天的内容就到这里结束噜🤪🤪🤪