二叉树 专题

文章目录

94 二叉树的中序遍历解题方法**迭代****递归** [101. 对称二叉树]解题方法**队列** [102. 二叉树的层序遍历]解题思路 [103. 二叉树的锯齿形层次遍历]主要思路 [104. 二叉树的最大深度]105 重建二叉树[108. 将有序数组转换为二叉搜索树][111. 二叉树的最小深度]**解题思路** 递归 [112. 路径总和][113. 路径总和 II]**解题思路及注意事项** [124. 二叉树中的最大路径和][144. 二叉树的前序遍历]**解题思路 递归与非递归****非递归** [145. 二叉树的后序遍历]解题思路同144的前序遍历 递归与非递归递归非递归 [199. 二叉树的右视图]主要解题思路往list中添加元素 当元素的个数==size的时候允许添加 [226. 翻转二叉树]解题思路 递归 [230. 二叉搜索树中第K小的元素]解题思路 [offer 07. 重建二叉树]解题思路 [Offer 26. 树的子结构]解题思路 递归

94 二叉树的中序遍历

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3] 1 2 / 3

输出: [1,3,2] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题方法

迭代

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while(curr!=null || !stack.isEmpty()){ while(curr!=null){ stack.push(curr); curr = curr.left; } curr = stack.pop(); res.add(curr.val); curr = curr.right; } return res; } }

递归

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); inorder(root,res); return res; } public void inorder(TreeNode root,List<Integer> res){ if(root==null){ return ; } inorder(root.left,res); res.add(root.val); inorder(root.right,res); } }

[101. 对称二叉树]

难度简单1054收藏分享切换为英文接收动态反馈

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1 / \ 2 2 / \ / \ 3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1 / \ 2 2 \ \ 3 3

解题方法

####进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

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

队列

class Solution { public boolean isSymmetric(TreeNode root) { return check(root,root); } public boolean check(TreeNode u,TreeNode v){ Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(u); q.offer(v); while(!q.isEmpty()){ u = q.poll(); v = q.poll(); if(u==null && v==null) continue; if((u==null || v==null)||(u.val!=v.val)){ return false; } q.offer(u.left); q.offer(v.right); q.offer(u.right); q.offer(v.left); } return true; } }

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

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例： 二叉树：[3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

返回其层次遍历结果：

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

解题思路

本题主要使用了队列的数据结构

class Solution { public List<List<Integer>> levelOrder(TreeNode root) { if(root==null) return new ArrayList<List<Integer>>(); List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(queue.size()>0){ //size为上一层节点的个数 int size = queue.size(); ArrayList<Integer> tmp = new ArrayList<>(); for(int i=0;i<size;++i){ TreeNode t = queue.remove(); tmp.add(t.val); if(t.left!=null) queue.add(t.left); if(t.right!=null) queue.add(t.right); } res.add(tmp); } return res; } }

[103. 二叉树的锯齿形层次遍历]

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如： 给定二叉树 [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

返回锯齿形层次遍历如下：

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

主要思路

用一个变量记录是在链表的头部添加还是尾部添加当一层遍历结束后往队列中添加一个 null当一层遍历结束之后 改变 变量的头部添加还是尾部添加 class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { if(root==null){ return new ArrayList<List<Integer>>(); } List<List<Integer>> result = new ArrayList<List<Integer>>(); LinkedList<TreeNode> node_queue = new LinkedList<TreeNode>(); node_queue.addLast(root); node_queue.addLast(null); LinkedList<Integer> level_list = new LinkedList<Integer>(); boolean is_order_left = true; while(node_queue.size()>0){ TreeNode curr_node = node_queue.pollFirst(); if(curr_node != null){ if(is_order_left) level_list.addLast(curr_node.val); else level_list.addFirst(curr_node.val); if(curr_node.left!=null) node_queue.addLast(curr_node.left); if(curr_node.right!=null) node_queue.addLast(curr_node.right); }else{ result.add(level_list); level_list = new LinkedList<Integer>(); if(node_queue.size()>0) // 记录这一层结束 node_queue.addLast(null); //翻转添加方向 is_order_left = !is_order_left; } } return result; } }

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

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

3

/ 9 20 / 15 7 返回它的最大深度 3 。

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

105 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

3

/ 9 20 / 15 7

限制：

0 <= 节点个数 <= 5000

class Solution { HashMap<Integer,Integer> dic = new HashMap<>(); int[] po; public TreeNode buildTree(int[] preorder, int[] inorder) { po = preorder; for(int i=0;i<inorder.length;i++){ dic.put(inorder[i],i); } return recur(0,0,inorder.length-1); } TreeNode recur(int pre_root,int in_left,int in_right){ if(in_left>in_right) return null; TreeNode root = new TreeNode(po[pre_root]); //i为根节点在中序遍历中的位置 int i= dic.get(po[pre_root]); //pre_root为 前序遍历中跟节点的位置 pre_root+1为左子树的根节点的位置 root.left = recur(pre_root+1,in_left,i-1); //i-in_left+1+pre_root为root.right节点的位置 root.right = recur(pre_root+i-in_left+1,i+1,in_right); return root; } }

[108. 将有序数组转换为二叉搜索树]

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5 class Solution { public TreeNode sortedArrayToBST(int[] nums) { return helper(nums,0,nums.length-1); } public TreeNode helper(int[] nums,int left,int right){ //当只有两个节点的时候left>right 奇数个节点left=right if(left>right){ return null; } int mid=(left+right)/2; TreeNode root = new TreeNode(nums[mid]); root.left = helper(nums,left,mid-1); root.right = helper(nums,mid+1,right); return root; } }

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

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

返回它的最小深度 2.

解题思路 递归

class Solution { public int minDepth(TreeNode root) { if(root==null) return 0; if(root.left==null && root.right==null) return 1; if(root.left==null) return 1+minDepth(root.right); if(root.right==null) return 1+minDepth(root.left); return 1+Math.min(minDepth(root.left),minDepth(root.right)); } } class Solution { public int minDepth(TreeNode root) { if(root==null){ return 0; } //该节点是否为叶子节点 if(root.left==null) return 1+minDepth(root.right); if(root.right==null) return 1+minDepth(root.left); //该节点不为叶子节点 return 1+Math.min(minDepth(root.left),minDepth(root.right)); } }

[112. 路径总和]

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root==null){ return false; } if(root.val==sum && root.left==null && root.right==null){ return true; } return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val); } }

[113. 路径总和 II]

难度中等356收藏分享切换为英文接收动态反馈

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

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1

返回:

[ [5,4,11,2], [5,8,4,5] ]

解题思路及注意事项

本题的主要思路是深度优先和回溯注意res.add(new ArrayList<>(path)); class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> res = new ArrayList<>(); if(root==null){ return res; } Deque<Integer> path = new ArrayDeque<>(); dfs(root,sum,path,res); return res; } private void dfs(TreeNode node,int sum,Deque<Integer> path,List<List<Integer>> res){ if(node==null){ return; } //是叶子节点 if(node.val==sum && node.left==null && node.right == null){ path.addLast(node.val); res.add(new ArrayList<>(path)); path.removeLast(); return; } path.addLast(node.val); dfs(node.left,sum-node.val,path,res); dfs(node.right,sum-node.val,path,res); path.removeLast(); } }

[124. 二叉树中的最大路径和]

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1：

输入：[1,2,3] 1 / \ 2 3 输出：6

示例 2：

输入：[-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 输出：42 class Solution { int maxval = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxval; } public int maxGain(TreeNode root){ if(root==null) return 0; int maxleft = Math.max(maxGain(root.left),0); int maxright = Math.max(maxGain(root.right),0); //判断一当前节点为根节点的是否形成一个最大路径 int maxtemp = root.val+maxleft+maxright; maxval = Math.max(maxval,maxtemp); //返回的左子路径或右子路径 return root.val+Math.max(maxleft,maxright); } }

[144. 二叉树的前序遍历]

难度中等377收藏分享切换为英文接收动态反馈

给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题思路 递归与非递归

递归写法非递归写法 需要借助栈 class Solution { List<Integer> ans = new ArrayList<>(); public List<Integer> preorderTraversal(TreeNode root) { preorderTraversall(root); return ans; } public void preorderTraversall(TreeNode root){ if(root==null){ return; } ans.add(root.val); preorderTraversall(root.left); preorderTraversall(root.right); } }

非递归

class Solution { List<Integer> ans = new ArrayList<Integer>(); public List<Integer> preorderTraversal(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); if(root==null) return ans; stack.push(root); while(!stack.isEmpty()){ TreeNode node = stack.pop(); if(node.right!=null){ stack.push(node.right); } if(node.left!=null){ stack.push(node.left); } ans.add(node.val); } return ans; } }

[145. 二叉树的后序遍历]

难度中等452收藏分享切换为英文接收动态反馈

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题思路同144的前序遍历 递归与非递归

递归

class Solution { List<Integer> ans = new ArrayList<>(); public List<Integer> postorderTraversal(TreeNode root) { postorderTraversall(root); return ans; } public void postorderTraversall(TreeNode root){ if(root==null){ return; } postorderTraversall(root.left); postorderTraversall(root.right); ans.add(root.val); } }

非递归

class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if (root == null) { return res; } Deque<TreeNode> stack = new LinkedList<TreeNode>(); TreeNode prev = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (root.right == null || root.right == prev) { res.add(root.val); prev = root; root = null; } else { stack.push(root); root = root.right; } } return res; } }

[199. 二叉树的右视图]

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释: 1 <--- / \ 2 3 <--- \ \ 5 4 <---

主要解题思路往list中添加元素 当元素的个数==size的时候允许添加

class Solution { public List<Integer> ans = new ArrayList<>(); public List<Integer> rightSideView(TreeNode root) { rightSideView(root,0); return ans; } public void rightSideView(TreeNode root,int level){ if(root==null) return; if(level==ans.size()){ ans.add(root.val); } level++; rightSideView(root.right,level); rightSideView(root.left,level); } }

[226. 翻转二叉树]

难度简单645收藏分享切换为英文接收动态反馈

翻转一棵二叉树。

示例：

输入：

4 / \ 2 7 / \ / \ 1 3 6 9

输出：

4 / \ 7 2 / \ / \ 9 6 3 1

备注: 这个问题是受到 Max Howell 的 原问题 启发的 ：

解题思路 递归

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

[230. 二叉搜索树中第K小的元素]

难度中等291收藏分享切换为英文接收动态反馈

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明： 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 1

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 3

进阶： 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

解题思路

二叉树的中序遍历

如果list中数量==k 返回这个数据就是第k小的元素

class Solution { public int kthSmallest(TreeNode root, int k) { ArrayList<Integer> nums = inorder(root,new ArrayList<Integer>(),k); return nums.get(k-1); } public ArrayList<Integer> inorder(TreeNode root,ArrayList<Integer> arr,int k){ if(root==null) return arr; if(arr.size()==k) return arr; inorder(root.left,arr,k); if(arr.size()==k) return arr; arr.add(root.val); inorder(root.right,arr,k); return arr; }

[offer 07. 重建二叉树]

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

3

/ 9 20 / 15 7

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

解题思路

本题的解题思路主要用到了一下几点

中序遍历有序性前序遍历 先遍历中间节点 后遍历又有两边的节点现将中序遍历的一值为k 索引为值 存储map中 在前序数组中获得 根节点的位置 以根节点的左侧构建左子树 右侧构建右子树 class Solution { HashMap<Integer,Integer> dic = new HashMap<>(); int[] po; public TreeNode buildTree(int[] preorder, int[] inorder) { po = preorder; for(int i=0;i<inorder.length;i++){ dic.put(inorder[i],i); } return recur(0,0,inorder.length-1); } TreeNode recur(int pre_root,int in_left,int in_right){ if(in_left>in_right) return null; TreeNode root = new TreeNode(po[pre_root]); int i= dic.get(po[pre_root]); root.left = recur(pre_root+1,in_left,i-1); //i-in_left+1+pre_root为root.right节点的位置 root.right = recur(pre_root+i-in_left+1,i+1,in_right); return root; } }

[Offer 26. 树的子结构]

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

3 / \

4 5 / 1 2 给定的树 B：

4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1] 输出：false 示例 2：

输入：A = [3,4,5,1,2], B = [4,1] 输出：true

解题思路 递归

递归

class Solution { public boolean isSubStructure(TreeNode A, TreeNode B) { return (A!=null && B!=null) && (recur(A,B)||isSubStructure(A.left,B)|| isSubStructure(A.right,B)); } boolean recur(TreeNode A,TreeNode B){ if(B==null) return true; if(A==null || A.val!=B.val) return false; return recur(A.left,B.left) && recur(A.right,B.right); } }