LeetCode——二叉树（Java）

二叉树

简介
[简单] 144. 二叉树的前序遍历、94. 二叉树的中序遍历、145. 二叉树的后序遍历
二叉树层序遍历
- [中等] 102. 二叉树的层序遍历
- [中等] 107. 二叉树的层序遍历 II
- [中等] 199. 二叉树的右视图
- [简单] 637. 二叉树的层平均值
- [中等] 429. N 叉树的层序遍历
- [中等] 515. 在每个树行中找最大值
- [中等] 116. 填充每个节点的下一个右侧节点指针、[中等]117. 填充每个节点的下一个右侧节点指针 II
- [简单] 104. 二叉树的最大深度
- [简单] 111. 二叉树的最小深度
[简单] 226. 翻转二叉树
[简单] 101. 对称二叉树
[简单] 100. 相同的树
[简单] 572. 另一棵树的子树
[简单] 222. 完全二叉树的节点个数
[简单] 110. 平衡二叉树
[简单] 257. 二叉树的所有路径
[简单] 404. 左叶子之和
[中等] 513. 找树左下角的值
[简单] 112. 路径总和
[中等] 113. 路径总和 II

简介

记录一下自己刷题的历程以及代码。写题过程中参考了代码随想录的刷题路线。会附上一些个人的思路，如果有错误，可以在评论区提醒一下。
涉及：二叉树前中后序遍历、层序遍历、队列Queue、头插法、递归、ArrayList、LinkedList、递归、StringBuilder

[简单] 144. 二叉树的前序遍历、94. 二叉树的中序遍历、145. 二叉树的后序遍历

144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历

前中后序遍历可以公用一套递归思路，都是比较经典的模板：

//先序遍历
递归访问(){
    对节点做操作
    递归访问(左子树)
    递归访问(右子树)
}

//中序遍历
递归访问(){
    递归访问(左子树)
    对节点做操作
    递归访问(右子树)
}

//后序遍历
递归访问(){
    递归访问(左子树)
    递归访问(右子树)
    对节点做操作
}

二叉树的前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> answer = new ArrayList<>();
        preorder(root, answer);
        return answer;
    }

    public void preorder(TreeNode root, List<Integer> answer){
        if(root == null) return;
        answer.add(root.val);
        preorder(root.left,answer);
        preorder(root.right,answer);
        return;
    }
}

二叉树的中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> answer = new ArrayList<>();
        inorder(root, answer);
        return answer;
    }

    public void inorder(TreeNode root, List<Integer> answer){
        if(root == null) return;
        inorder(root.left,answer);
        answer.add(root.val);
        inorder(root.right,answer);
        return;
    }
}

二叉树的后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> answer = new ArrayList<>();
        postorder(root, answer);
        return answer;
    }

    public void postorder(TreeNode root, List<Integer> answer){
        if(root == null) return;
        postorder(root.left,answer);
        postorder(root.right,answer);
        answer.add(root.val);
        return;
    }
}

二叉树层序遍历

[中等] 102. 二叉树的层序遍历

原题链接

经典的BFS
用队列保存树节点，每次统计队列的size()，也就是第n层节点数量。
处理这一层的节点，将其子节点全部加入队列，循环往复到队列为空。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root == null) return ans;
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> nums = new ArrayList<Integer>();
            int k = queue.size();
            while(k-- > 0) {
                TreeNode temp = queue.remove();
                nums.add(temp.val);
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
            }
            ans.add(nums);
        }
        return ans;
    }
}

[中等] 107. 二叉树的层序遍历 II

原题链接

方法①：
与102的最基本的层序遍历相似的逻辑，使用递归的方法把每次ans.add(nums);操作顺序进行了倒序。

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root == null) return ans;
        queue.add(root);
        recursion(queue, ans);
        return ans;
    }

    public void recursion(Queue<TreeNode> queue, List<List<Integer>> ans){
        if(!queue.isEmpty()){
            List<Integer> nums = new ArrayList<Integer>();
            int k = queue.size();
            while(k-- > 0) {
                TreeNode temp = queue.remove();
                nums.add(temp.val);
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
            }
            recursion(queue, ans);
            ans.add(nums);
        }
        return;
    }
}

方法②：
使用LinkedList，用头插法的方式构造返回值。（LinkedList底层为链表，头插法比较方便，ArrayList底层是连续存储，头插法复杂度为O(n)）

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root == null) return ans;
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> nums = new ArrayList<Integer>();
            int k = queue.size();
            while(k-- > 0) {
                TreeNode temp = queue.remove();
                nums.add(temp.val);
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
            }
            ans.add(0, nums);
        }
        return ans;
    }

}

[中等] 199. 二叉树的右视图

原题链接

与102的最基本的层序遍历相似的逻辑，构建返回值时每次只把当前层最右边的数加入ans即可。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root == null) return ans;
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> nums = new ArrayList<Integer>();
            int k = queue.size();
            while(k-- > 0) {
                TreeNode temp = queue.remove();
                nums.add(temp.val);
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
            }
            ans.add((nums.get(nums.size()-1)));
        }
        return ans;
    }
}

[简单] 637. 二叉树的层平均值

原题链接

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        List<Double> ans = new ArrayList<>();
        if(root == null) return ans;
        queue.add(root);
        while(!queue.isEmpty()){
            double num = 0;
            int k = queue.size();
            int i = k;
            while(k-- > 0){
                TreeNode temp = queue.remove();
                num += temp.val;
                if(temp.left != null) queue.add(temp.left);
                if(temp.right != null) queue.add(temp.right);
            }
            ans.add(num / i);
        }
        return ans;
    }
}

[中等] 429. N 叉树的层序遍历

原题链接

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Queue<Node> queue = new ArrayDeque<>();
        if(root == null) return ans;
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> nums = new ArrayList<Integer>();
            int k = queue.size();
            while(k-- > 0) {
                Node temp = queue.remove();
                nums.add(temp.val);
                for(int i = 0; i < temp.children.size(); i++) {
                    queue.add(temp.children.get(i));
                }
            }
            ans.add(nums);
        }
        return ans;
    }
}

[中等] 515. 在每个树行中找最大值

原题链接

class Solution {
    public List<Integer> largestValues(TreeNode root) {
       List<Integer> ans = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root == null) return ans;
        queue.add(root);
        while(!queue.isEmpty()){
            int max = queue.peek().val;
            int k = queue.size();
            while(k-- > 0) {
                TreeNode temp = queue.remove();
                max = max > temp.val ? max : temp.val;
                if(temp.left != null) queue.add(temp.left);
                if(temp.right != null) queue.add(temp.right);
            }
            ans.add(max);
        }
        return ans;
    }
}

[中等] 116. 填充每个节点的下一个右侧节点指针、[中等]117. 填充每个节点的下一个右侧节点指针 II

[中等] 116. 填充每个节点的下一个右侧节点指针
[中等]117. 填充每个节点的下一个右侧节点指针 II
方法①：
正常的层序遍历，每层除了最后一个节点之外都对next赋值

class Solution {
    public Node connect(Node root) {
       List<Integer> ans = new ArrayList<>();
        Queue<Node> queue = new ArrayDeque<>();
        if(root == null) return root;
        queue.add(root);
        while(!queue.isEmpty()){
            int k = queue.size();
            while(k-- > 0) {
                Node temp = queue.remove();
                if(k > 0) {
                    temp.next = queue.peek();
                }
                if(temp.left != null) queue.add(temp.left);
                if(temp.right != null) queue.add(temp.right);
            }
            
        }
        return root;
    }
}

方法②：
使用next链接来对同层次节点做遍历，可以省去队列的开销
注意Node引用需要申请在方法外，不能做参数传递，java中都是值传递

class Solution {
    Node last = null, nextStart = null;
    public Node connect(Node root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null) return root;

        Node p = root;
        while(p!=null){
            if(p.left != null){
                handle(p.left);
            }
            if(p.right != null){
                handle(p.right);
            }
            p = p.next;
            if(p == null && nextStart != null){
                p = nextStart;
                nextStart = null;
                last = null;
            }
        }
        return root;
    }

    public void handle(Node p){
        if(nextStart == null){
            nextStart = p;
        }
        if(last != null){
            last.next = p;
        }
        last = p;
    }

}

[简单] 104. 二叉树的最大深度

原题链接

方法①：层序遍历

class Solution {
    public int maxDepth(TreeNode root) {
        int depth = 0;
        if(root == null) return depth;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()){
            depth++;
            int k = queue.size();
            while(k-- > 0) {
                TreeNode temp = queue.remove();
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
            }
        }
        return depth;
    }
}

方法②：递归
树的高度就是其子树的最大高度 + 1，用在多叉树上也是一样的思路

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
    }
}

[简单] 111. 二叉树的最小深度

原题链接
方法①：层序遍历找左右子树皆空的点即可

class Solution {
    public int minDepth(TreeNode root) {
        int depth = 0;
        if(root == null) return depth;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()){
            depth++;
            int k = queue.size();
            while(k-- > 0) {
                TreeNode temp = queue.remove();
                if(temp.left == null && temp.right == null) return depth;
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
            }
        }
        return depth;
    }
}

方法②：递归求解
用递归求解记住需要的是到叶子节点的深度
如果非叶子节点，假设只有单边左子树，右子数应当是找不到叶子节点也就是距离无穷大，可以设置一个Integer.MAX_VALUE做为返回值，这样通过比较，递归的上一层就会获得左子树找到叶子节点的最小距离 + 1

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        int leftMin = Integer.MAX_VALUE;
        int rightMin = Integer.MAX_VALUE;
        if(root.left != null) leftMin = minDepth(root.left);
        if(root.right != null) rightMin = minDepth(root.right);
        return (leftMin < rightMin ? leftMin : rightMin) + 1;
    }
}

[简单] 226. 翻转二叉树

原题链接

前序遍历的基础上每一次遍历节点做翻转操作。
切记前序、后续、层次遍历都可以，但是不可以是中序遍历，因为中序遍历是左中右 的顺序，递归调整左子树之后，处理当前节点会把左右子树对调，这样进入右子数递归时其实还是对原先的左子树做操作。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        preorder(root);
        return root;
    }

    public void preorder(TreeNode root){
        if(root == null) return;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        preorder(root.left);
        preorder(root.right);
        return;
    }
}

[简单] 101. 对称二叉树

原题链接

经典的递归思路，对左右子树做反方向的递归即可，在左子树上做前序遍历，每次递归left的左节点时就去递归right的右节点，递归left的右节点时则递归right的左节点。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        TreeNode left = root.left;
        TreeNode right = root.right;
        return recursion(left, right);
    }

    public boolean recursion(TreeNode left, TreeNode right){
        if(left == null && right == null)
            return true;
        else if(left != null && right != null) {
            if (left.val != right.val)
                return false;
            if (recursion(left.left, right.right) && recursion(left.right, right.left))
                return true;
        }
        return false;
    }
}

[简单] 100. 相同的树

原题链接

两棵树同频做前序遍历即可，其他遍历方式也是ok的。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return recursion(p, q);
    }

    public boolean recursion(TreeNode p, TreeNode q){
        if(p == null && q == null)
            return true;
        else if(p != null && q != null) {
            if (p.val != q.val)
                return false;
            if (recursion(p.left, q.left) && recursion(p.right, q.right))
                return true;
        }
        return false;
    }
}

[简单] 572. 另一棵树的子树

原题链接

两层递归
①preorder：对root 的前序遍历，找到与subRoot相同值的节点，作为比较的起点②cmprecursion：对root的节点以及subRoot的根节点做同频前序遍历对比

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(subRoot == null) return true;
        if(root == null) return true;
        return preorder(root, subRoot);
    }

    public boolean preorder(TreeNode p, TreeNode q){
        if(p == null) return false;
        if(p.val == q.val && cmprecursion(p, q))
            return true;
        if(preorder(p.left, q) || preorder(p.right, q)) 
            return true;
        return false;
    }

    public boolean cmprecursion(TreeNode p, TreeNode q){
        if(p == null && q == null) 
            return true;
        else if(p != null && q != null){
            if(p.val != q.val) 
                return false;
            if(cmprecursion(p.left, q.left) && cmprecursion(p.right, q.right))
                return true;
        }
        return false;
    }
}

[简单] 222. 完全二叉树的节点个数

原题链接

递归

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

[简单] 110. 平衡二叉树

原题链接

递归，后序遍历
用-2标记以当前节点为根节点的子树非平衡二叉树，在递归中一旦出现-2就层层传递到root，用来标识存在子树为非平衡二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(countDepth(root) == -2) return false;
        return true;
    }

    public int countDepth(TreeNode p){
        if(p == null) return 0;
        int leftDepth = countDepth(p.left);
        int rightDepth = countDepth(p.right);
        int flag = leftDepth - rightDepth;
        if(leftDepth == -2 || rightDepth == -2 || flag > 1 || flag < -1) return -2;
        else return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
    }
}

[简单] 257. 二叉树的所有路径

原题链接

思路就是DFS深度优先遍历找到每一条路径，效率差异主要体现在对字符串拼接的处理上，使用StringBuilder会更高效一些。
在这里插入图片描述

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ans = new ArrayList<>();
        if(root == null) return ans;
        DFS(root, ans, "");
        return ans;
    }

    public void DFS(TreeNode p, List<String> ans, String string){
        StringBuilder sb = new StringBuilder(string);
        sb.append(p.val);
        if(p.left == null && p.right == null){
            ans.add(sb.toString());
            return;
        }
        sb.append("->");
        if(p.left != null)
            DFS(p.left, ans, sb.toString());
        if(p.right != null)
            DFS(p.right, ans, sb.toString());
    }
}

[简单] 404. 左叶子之和

原题链接

在前序遍历的基础上更改，用一个布尔类型标记当前节点是否是某个节点的左孩子

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        int sum = preorder(root, false, 0);
        return sum;
    }

    public int preorder(TreeNode root, boolean isLChild, int sum) {
        if (root == null) return sum;
        if (root.left == null && root.right == null && isLChild){
            return sum + root.val;
        }
        return preorder(root.left, true, sum) + preorder(root.right, false, sum);
    }
}

[中等] 513. 找树左下角的值

原题链接

最容易想到就是层序遍历，每层都记录队列头的值即可

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        int ans = root.val;
        queue.add(root);
        while(!queue.isEmpty()){
            int k = queue.size();
            ans = queue.peek().val;
            while(k-- > 0) {
                TreeNode temp = queue.remove();
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
            }
        }
        return ans;
    }
}

方法②：稍微绕一些，使用前序遍历，每次碰到新的maxDepth，都是左子树先，所以，只要碰到新的最大深度就可以更新返回值

class Solution {
    int maxDepth = -1;
    int value = 0;

    public int findBottomLeftValue(TreeNode root) {
        preorder(root, 0);
        return value;
    }

    public void preorder(TreeNode node, int depth) {
        // 终止条件: 遇到叶子结点就可以return了。
        // 并且：当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。
        if (node.left == null && node.right == null) {
            if (maxDepth < depth) {
                maxDepth = depth;
                value = node.val;
            }
            return;
        }

        // 递归遍历左子树
        if (node.left != null) {
            preorder(node.left, depth + 1);
        }

        // 递归遍历右子树
        if (node.right != null) {
            preorder(node.right, depth + 1);
        }
    }
}

[简单] 112. 路径总和

原题链接

前序遍历，记得总和与目标值相当时还需要判断是否是叶子节点，否则并不是一组答案

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return preOrder(root, 0 ,targetSum);
    }

    public boolean preOrder(TreeNode root, int sum, int targetSum){
        if(root == null) return false;
        sum = sum + root.val;
        if(sum == targetSum && root.left == null && root.right == null)
            return true;
        if(preOrder(root.left, sum, targetSum)) return true;
        if(preOrder(root.right, sum, targetSum)) return true;
        return false;
    }
}

[中等] 113. 路径总和 II

原题链接

前序遍历，记得总和与目标值相当时还需要判断是否是叶子节点，否则并不是一组答案

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> answer = new ArrayList<>();
        preOrder(root, ans, answer, 0, targetSum);
        return ans;
    }

    public void preOrder(TreeNode root, List<List<Integer>> ans, List<Integer> answer, int sum, int targetSum){
        if(root == null) return;
        sum = sum + root.val;
        answer.add(root.val);
        if(sum == targetSum && root.left == null && root.right == null)
            ans.add(new ArrayList<>(answer));
        preOrder(root.left, ans, answer, sum, targetSum);
        preOrder(root.right, ans, answer, sum, targetSum);
        answer.remove(answer.size() - 1);
    }
}