二叉树
算法
|
|
|
139

2629 字
|
27 分钟

二叉树

1. LeetCode 102. 二叉树的层序遍历

题目地址：LeetCode

image-20230810221716502

image-20230810221729001

[
  [3],
  [9,20],
  [15,7]
]

解题思路：

  1. 特例处理：当根节点为空，则返回空列表[]
  2. 初始化：打印结果列表res = []，包含根节点的队列 queue = [root]
  3. BFS 循环：当队列 queue 为空时跳出

​ a. 新建一个临时列表 temp ，用于存储当前层打印结果

​ b. 当前层打印循环： 循环次数为当前层节点数（即队列 queue 长度）

​ a. 出队： 队首元素出队，记为 node

​ b. 打印： 将 node.val 添加至 temp 尾部

​ c. 添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue

​ c. 将当前层结果 temp 添加入 res

  1. 返回值： 返回打印结果列表 res 即可
/**
 * 二叉树的层次遍历
 *
 * @author Enndfp
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if (root != null) queue.add(root);

        while (!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            res.add(temp);
        }
        return res;
    }
}

2. LeetCode 107. 二叉树的层序遍历 II

题目地址：LeetCode

image-20231104094005306

[
  [15,7],
  [9,20],
  [3]
]

解题思路：

  • 本题同上一题基本一样，只不过要求返回结果是逆序的，可以在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的头部
class Solution{
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if(root != null) queue.add(root);

        while(!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(0,temp);
        }
        return res;
    }
}

3. LeetCode 103. 二叉树的锯齿形层序遍历

题目地址：LeetCode

image-20230815215037519

image-20230815215049858

[
  [3],
  [20,9],
  [15,7]
]

解题思路：

  • 利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列） temp ，并规定：
    • 奇数层 则添加至 temp 尾部
    • 偶数层 则添加至 temp 头部

注意

本题通过 res 里的元素个数来判断是奇数层还是偶数层

  • res.size() % 2 == 0 说明 res 里面的元素为偶数个，即当前循环为奇数层
  • res.size() % 2 != 0 说明 res 里面的元素为奇数个，即当前循环为偶数层
/**
 * 二叉树的锯齿形层次遍历
 *
 * @author Enndfp
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if (root != null) queue.add(root);

        while (!queue.isEmpty()) {
            LinkedList<Integer> temp = new LinkedList<>();

            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if (res.size() % 2 == 0) temp.addLast(node.val);
                else temp.addFirst(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            res.add(temp);
        }
        return res;
    }
}

4. LeetCode 429. N 叉树的层序遍历

题目地址：LeetCode

image-20231105155924078

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();

        if(root != null) queue.add(root);

        while(!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--){
                Node node = queue.poll();
                temp.add(node.val);
                for(Node child: node.children){
                    if(child != null){
                        queue.add(child);
                    }
                }
            }
            res.add(temp);
        }
        return res;
    }
}

5. LeetCode 515. 在每个树行中找最大值

题目地址：LeetCode

image-20231105161607670

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if(root != null) queue.add(root);

        while(!queue.isEmpty()){
            int max = Integer.MIN_VALUE;
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                max = Math.max(max,node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(max);
        }
        return res;
    }
}

6. LeetCode 637. 二叉树的层平均值

题目地址：LeetCode

image-20231105163336024

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if(root != null) queue.add(root);

        while(!queue.isEmpty()){
            Double sum = 0D;
            int len = queue.size();
            for(int i = len; i > 0; i--){
                TreeNode node = queue.poll();
                sum += node.val;
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(sum / len);
        }
        return res;
    }
}

7. LeetCode 199. 二叉树的右视图

题目地址：LeetCode

image-20231105165915655

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if(root != null) queue.add(root);

        while(!queue.isEmpty()){
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                if(i == 1) res.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
        }
        return res;
    }
}

8. LeetCode 513. 找树左下角的值

题目地址：LeetCode

image-20231105170513758

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int res = 0;
        Queue<TreeNode> queue = new LinkedList<>();

        if(root != null) queue.add(root);

        while(!queue.isEmpty()){
            int len = queue.size();
            for(int i = len; i > 0; i--){
                TreeNode node = queue.poll();
                if(i == len) res = node.val;
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
        }
        return res;
    }
}

9. LeetCode 144. 二叉树的前序遍历

题目地址：LeetCode

image-20231106142435954

解题思路：

  • 初始化栈，并将根节点入栈
  • 当栈不为空时：
    • 弹出栈顶元素 root，并将值添加到结果中
    • 如果 root 的右子树非空，将右子树入栈
    • 如果 root 的左子树非空，将左子树入栈

由于栈是“先进后出”的顺序，所以入栈时先将右子树入栈，这样使得前序遍历结果为 “根->左->右”的顺序

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        if(root != null) stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }
        return res;
    }
}

10. LeetCode 94. 二叉树的中序遍历

题目地址：LeetCode

image-20231106151131447

解题思路：

image-20231106151203401

image-20231106151236142

image-20231106151251575

image-20231106151304052

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root= stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

11. LeetCode 145. 二叉树的后序遍历

题目地址：LeetCode

image-20231106152340147

解题思路：

如下图，我们先观察后序遍历的结果是 seq = {9 5 7 4 3}，如果我们将其整体反转的话就是 new_seq = {3 4 7 5 9}

image.png

我们可以发现要得到 new_seq 的方法和前序遍历思路几乎一致，只不过是左右反了。前序是先中间，再左边然后右边，而这里是先中间，再右边然后左边。那我们完全可以改造一下前序遍历，得到序列 new_seq 之后再 reverse 一下就是想要的结果了

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        if(root != null) stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.left != null) stack.push(node.left);
            if(node.right != null) stack.push(node.right);
        }
        Collections.reverse(res);
        return res;
    }
}

12. LeetCode 100. 相同的树

题目地址：LeetCode

image-20231107105701177

解题思路：

  1. 如果两个二叉树都为空，则两个二叉树相同

  2. 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同

  3. 如果两个二叉树都不为空

    • 首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同

    • 若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

13. LeetCode 101. 对称二叉树

题目地址：LeetCode

image-20231107111234605

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

    private boolean check(TreeNode p, TreeNode q){
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        return check(p.left,q.right) && check(p.right,q.left);
    }
}

14. LeetCode 617. 合并二叉树

题目地址：LeetCode

image-20231107112324670

解题思路：

可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并

两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式

  • 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空
  • 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点
  • 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点

对一个节点进行合并之后，还要对该节点的左右子树分别进行合并。这是一个递归的过程

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;

        TreeNode merged = new TreeNode(root1.val + root2.val);
        merged.left = mergeTrees(root1.left,root2.left);
        merged.right = mergeTrees(root1.right,root2.right);
        return merged;
    }
}

15. LeetCode 257. 二叉树的所有路径

题目地址：LeetCode

image-20231108204901047

解题思路：

在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点

  • 如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可
  • 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点

如此，当遍历完整棵二叉树以后我们就得到了所有从根节点到叶子节点的路径

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        dfs(root,"",res);
        return res;
    }

    private void dfs(TreeNode root, String path, List<String> res){
        if(root == null) return;
        if(root.left == null && root.right == null){
            res.add(path + root.val);
        }
        dfs(root.left,path + root.val + "->", res);
        dfs(root.right,path + root.val + "->", res);
    }
}

16. LeetCode 112. 路径总和

题目地址：LeetCode

image-20231108211019293

解题思路：

假定从根节点到当前节点的值之和为 val，我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val

不难发现这满足递归的性质：

  • 若当前节点就是叶子节点，那么我们直接判断 sum 是否等于 val 即可（因为路径和已经确定，就是当前节点的值，我们只需要判断该路径和是否满足条件）
  • 若当前节点不是叶子节点，我们只需要递归地询问它的子节点是否能满足条件即可
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        if(root.left == null && root.right == null){
            return targetSum == root.val;
        }
        boolean left = hasPathSum(root.left,targetSum - root.val);
        boolean right = hasPathSum(root.right,targetSum - root.val);
        return left || right;
    }
}

17. LeetCode 226. 翻转二叉树

题目地址：LeetCode

image-20231109092135039

解题思路：

我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;

        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;

        return root;
    }
}

18. LeetCode 104. 二叉树的最大深度

题目地址：LeetCode

image-20231109095612011

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        return Math.max(leftHeight, rightHeight) + 1;
    }
}

19. LeetCode 110. 平衡二叉树

题目地址：LeetCode

image-20231112210929101

知识补充：

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

img

当前 树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 + 1

解题思路：

  • 返回值：

    1. 当节点 root 左/右子树的深度差 <=1，则返回当前子树的深度，即节点 root 的左/右子树的深度最大值 +1（max（left，right）+ 1）

    2. 当节点 root 左/右子树的深度差 >1，则返回 −1，代表此子树不是平衡树

  • 终止条件：

    1. 当 root 为空：说明越过叶节点，因此返回高度 0
    2. 当左（右）子树深度为 −1，代表此树的左（右）子树不是平衡树，因此截止，直接返回 -1
class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root){
        if(root == null) return 0;

        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;

        return Math.abs(left - right) < 2 ? Math.max(left,right) + 1 : -1;
    }
}

20. LeetCode 111. 二叉树的最小深度

题目地址：LeetCode

image-20231113141654000

解题思路：

  1. 当前节点 root 为空时，说明此处树的高度为 0，0 也是最小值
  2. 当前节点 root 的左子树和右子树都为空时，说明此处树的高度为 1，1 也是最小值
  3. 如果为其他情况，则说明当前节点有值，且需要分别计算其左右子树的最小深度，返回最小深度 +1，+1 表示当前节点存在有 1 个深度
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null){
            return 1;
        }
        int min_depth = Integer.MAX_VALUE;
        if(root.left != null){
            min_depth = Math.min(minDepth(root.left),min_depth);
        }
        if(root.right != null){
            min_depth = Math.min(minDepth(root.right),min_depth);
        }
        return min_depth + 1;
    }
}

21. LeetCode 559. N 叉树的最大深度

题目地址：LeetCode

image-20231113143917266

class Solution {
    public int maxDepth(Node root) {
        if(root == null) return 0;

        int maxChildren = 0;
        List<Node> children = root.children;
        for(Node child: children){
            int childDepth = maxDepth(child);
            maxChildren = Math.max(childDepth,maxChildren);
        }

        return maxChildren + 1;
    }
}
🌟 如果您喜欢我的文章，欢迎赞赏支持，您的支持是我创作的最大动力！🌟
🖋 作者：Enndfp
🔗链接：https://blog.enndfp.cn
📜版权声明：您可以自由转载，但请务必注明原文地址，感谢您的尊重与支持~
算法
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
队列和Hash

							
							

							
栈

							
							

							
数组

							
							

							
链表