数据结构树（二叉树的10大使用实例详解）

一、翻转二叉树

题目描述

链接
翻转一棵二叉树。

示例：

输入：

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

输出：

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

方法一 递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) return null; TreeNode right = invertTree(root.right); TreeNode left = invertTree(root.left); root.left = right; root.right = left; return root; } } 

方法二 迭代

类似于层序遍历或者广度优先搜索，然后把每一层的节点进行翻转

 4                            4                    4
   /   \                         / \                  / \
  2     7       ——>             7   2      ——>       7   2   
 / \   / \                     / \   / \            / \ / \
1   3 6   9                   6  9  1   3          9   63  1 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) return null; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()) { TreeNode curr = queue.poll(); //交换curr节点的左右子树 TreeNode temp = curr.left; curr.left = curr.right; curr.right = temp; if(curr.left != null) queue.offer(curr.left); if(curr.right != null) queue.offer(curr.right); } return root; } } 

---

二叉树的遍历

二、验证二叉搜索树

题目描述

题目链接

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
    2
   / \
  1   3
输出: true 

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。 

方法一 递归

二叉搜索树的性质是：如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
那么我们可以考虑构造一个递归函数进行判断：

1. 根节点的左子树小于根节点
2. 根节点的右子树大于根节点
3. 其左右子树是否是二叉搜索树，由递归进行判断。

因此构造递归函数 $helper(root, max, min)$，表示以$root$为根的子树，判断其书中的所有节点值是否在$（min,max）$之间。如果$root$的值不在$（min，max）$之间，说明不满足条件，直接返回；反之，我们要递归检查左右子树是否满足二叉搜索树的条件。

1. 递归调用当前根节点的左子树时，需要把上界改为当前根节点的值，即$helper(root.left, root.val, min)$
2. 递归调用当前根节点的右子树时，需要把下界改为当前根节点的值，即$helper(root.left, max, root.val)$.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public boolean isValidBST(TreeNode root) { return helper(root, null, null); } private boolean helper(TreeNode root, Integer max, Integer min){ if(root == null) return true; if((min != null && root.val <= min) || (max != null && root.val >= max)) return false; return helper(root.left, root.val, min) && helper(root.right, max, root.val); } } 

方法二 中序遍历

中序遍历的顺序是：左子树->根->右子树，二叉搜索树的中序遍历结果必然是升序的。在进行中序遍历时，判断当前遍历到的值小于等于上一个遍历到的值则违背了二叉搜索树的规则，返回false。
注意：
这里添加了一个哨兵值（最小值），以便遍历第一个元素时，第一个元素必定大于这个哨兵值。
哨兵值得设置就需要注意一下坑了。
首先设置为Integer.MIN_VALUE,大小为-2³¹，即-2147483648。但偏偏测试数据里就有-2147483648这么小的数据，那么不能这样设置。
可以设置成 -Double.MAX_VALUE,其大小为 (2-2^-52)·2¹⁰²³，同时需要注意的是Double.MIN_VALUE的值为2^-1074,并非是负数。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public boolean isValidBST(TreeNode root) { //中序遍历为：左-中-右 Stack<TreeNode> stack = new Stack<>(); double pre = -Double.MAX_VALUE; if(root != null) stack.push(root); while(!stack.isEmpty()){ TreeNode curr = stack.pop(); if(curr != null){ if(curr.right != null) stack.push(curr.right); stack.push(curr); stack.push(null); if(curr.left != null) stack.push(curr.left); }else{ int now = stack.pop().val; if(now <= pre){ return false; }else{ pre = now; } } } return true; } } 

三、二叉树的最大深度

题目描述

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

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

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

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

 3
   / \
  9  20
    /  \
   15   7 

返回它的最大深度 3 。

方法一、递归，DFS

一条条路径进行搜索，找到最长的那条路径。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; int leftH = maxDepth(root.left); int rightH = maxDepth(root.right); return Math.max(leftH, rightH) + 1; } } 

方法二、BFS

一层层搜索树，每搜索处理一层，层数加1,最后一层的就是最深的一层，返回当前层数即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; int maxHeight = 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); for(int i = 0; i < size; i++){//处理当前层所有节点 TreeNode curr = queue.poll(); if(curr.left != null) queue.offer(curr.left); if(curr.right != null) queue.offer(curr.right); } maxHeight += 1; } return maxHeight; } } 

---

四、二叉树的最小深度

题目描述

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

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

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

示例:

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

 3
   / \
  9  20
    /  \
   15   7 

返回它的最小深度 2.

方法一、BFS

广度优先搜索，一层层处理，当处理到一个节点的左右子树都为空时，该节点就是最小深度的节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public int minDepth(TreeNode root) { if(root == null) return 0; int minHeight = 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); for(int i = 0; i < size; i++){//处理当前层所有节点 TreeNode curr = queue.poll(); if(curr.left == null && curr.right == null) return minHeight + 1;//返回结果 if(curr.left != null) queue.offer(curr.left); if(curr.right != null) queue.offer(curr.right); } minHeight += 1; } return minHeight;//这里返回什么不重要，仅仅保证语法的正确 } } 

方法二 DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public int minDepth(TreeNode root) { if(root == null) return 0; if(root.left == null && root.right == null) return 1; int minH = Integer.MAX_VALUE; if(root.left != null) minH = Math.min(minDepth(root.left),minH); if(root.right != null) minH = Math.min(minDepth(root.right),minH); return minH + 1; } } 

另一写法

• 当 root 节点左右孩子都为空时，返回 1
• 当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
• 当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public int minDepth(TreeNode root) { if(root == null) return 0; if(root.left == null && root.right == null) return 1; int leftH = minDepth(root.left); int rightH = minDepth(root.right); if(root.left == null || root.right == null)//左右子树有一个为空 return leftH + rightH + 1;//leftH和rightH中有一个为0 return Math.min(leftH, rightH) + 1; } } 

五、二叉树的层序遍历

题目描述

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

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

 3
   / \
  9  20
    /  \
   15   7 

返回其层次遍历结果：

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

BFS

广度优先搜索

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); if(root == null) return list; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); List<Integer> currLevel = new ArrayList<>(); for(int i = 0; i < size; i++){ TreeNode curr = queue.poll(); currLevel.add(curr.val); if(curr.left != null) queue.offer(curr.left); if(curr.right != null) queue.offer(curr.right); } list.add(currLevel); } return list; } } 

---

六、二叉树的序列化与反序列化

题目描述

题目链接
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

你可以将以下二叉树：

1 

/
2 3
/
4 5

序列化为 “[1,2,3,null,null,4,5]”

方法一、BFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { //BFS，层序遍历 if(root == null) return ""; StringBuilder sb = new StringBuilder(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ TreeNode curr = queue.poll(); if(curr == null){ sb.append("n "); continue; } sb.append(curr.val + " "); queue.offer(curr.left); queue.offer(curr.right); } return sb.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data == "") return null; Queue<TreeNode> queue = new LinkedList<>(); String[] values = data.split(" "); TreeNode root = new TreeNode(Integer.parseInt(values[0])); queue.offer(root); for(int i = 1; i < values.length; i++){ TreeNode parent = queue.poll(); if(!values[i].equals("n")){ TreeNode left = new TreeNode(Integer.parseInt(values[i])); parent.left = left; queue.offer(left); } if(!values[++i].equals("n")){ TreeNode right = new TreeNode(Integer.parseInt(values[i])); parent.right = right; queue.offer(right); } } return root; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root)); 

方法二、DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null) return "n ";//序列用空格隔开，所以n后要加空格 //前序遍历的顺序 ： 根 ——左——右  return root.val + " " + serialize(root.left) + serialize(root.right); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { String[] values = data.split(" "); Queue<String> queue = new LinkedList<>(Arrays.asList(values)); return dfs(queue); } private TreeNode dfs(Queue<String> queue){ String curr = queue.poll(); if(curr.equals("n")) return null; TreeNode parent = new TreeNode(Integer.parseInt(curr)); parent.left = dfs(queue); parent.right = dfs(queue); return parent; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root)); 

---

七、二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。 

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。 

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

方法一、递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (p.val > root.val && q.val > root.val) //p,q节点都大于根节点 return lowestCommonAncestor(root.right, p ,q); if (p.val < root.val && q.val < root.val) //p,q节点都小于根节点 return lowestCommonAncestor(root.left, p ,q); return root; //p,q一个大于root，一个小于root，当前的root即为最近公共祖先 } } 

方法二、迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (root != null) { if (p.val > root.val && q.val > root.val) root = root.right; else if (p.val < root.val && q.val < root.val) root = root.left; else return root; } return null; } } 

---

八、二叉树的最近公共祖先

题目描述

题目链接
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。 

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

递归、后续遍历

如果 root 是 p, q 的 最近公共祖先 ，有以下3种情况：

1. p 和 q 分别在 root 的左右子树中
2. p = root，且 q 在 root的子树中
3. q = root ，且 p 在 root 的子树中

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if ( root == null || root == p || root == q)//递归终止条件 return root; TreeNode leftTree = lowestCommonAncestor(root.left, p, q);//左子树 TreeNode rightTree = lowestCommonAncestor(root.right, p, q);//右子树 /*
        1. left，right同时为空，则root的左右子树都不包含p，q
        2. left，right同时非空，说明p，q分别位于root的左右子树中，root为最近公共祖先
        3. left为空，right非空，说明p，q不在root的左子树，返回right
        4. left非空，right为空，说明p，q不在root的右子树，返回left
        */ if(leftTree == null) return rightTree; if(rightTree == null) return leftTree; return root; } } 

九、从前序与中序遍历序列构造二叉树

题目描述

题目链接
根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7] 

返回如下的二叉树：

 3
   / \
  9  20
    /  \
   15   7 

递归法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0 || preorder.length != inorder.length) { return null; } return buildTreeHelp(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1); } private TreeNode buildTreeHelp(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd){ if(preStart > preEnd || inStart > inEnd) return null; TreeNode root = new TreeNode(preorder[preStart]);//前序遍历的第一个元素为root节点 int inMid = inStart;//在中序遍历序列中找到root节点，root节点之前的是左子树，之后的是右子树 while(inorder[inMid] != root.val){ inMid++; } int leftNums = inMid - inStart; //root的左子树节点数量 root.left = buildTreeHelp(preorder, inorder, preStart + 1, preStart + leftNums, inStart, inMid - 1); root.right = buildTreeHelp(preorder, inorder, preStart + leftNums + 1, preEnd, inMid + 1, inEnd); return root; } } 

十、从中序与后序遍历序列构造二叉树

题目描述

链接
根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3] 

返回如下的二叉树：

 3
   / \
  9  20
    /  \
   15   7 

递归法

方法同105题一样

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if (postorder == null || postorder.length == 0 || inorder == null || inorder.length == 0 || postorder.length != inorder.length) { return null; } return buildTreeHelp(postorder, inorder, 0, postorder.length - 1, 0, postorder.length - 1); } private TreeNode buildTreeHelp(int[] postorder, int[] inorder, int postStart, int postEnd, int inStart, int inEnd){ if(postStart > postEnd || inStart > inEnd) return null; TreeNode root = new TreeNode(postorder[postEnd]);//后序遍历的最后一个元素为root节点 int inMid = inStart;//在中序遍历序列中找到root节点，root节点之前的是左子树，之后的是右子树 while(inorder[inMid] != root.val){ inMid++; } int leftNums = inMid - inStart; //root的左子树节点数量 root.left = buildTreeHelp(postorder, inorder, postStart, postStart + leftNums - 1, inStart, inMid - 1); root.right = buildTreeHelp(postorder, inorder, postStart + leftNums, postEnd - 1, inMid + 1, inEnd); return root; } } 

本文地址：https://blog.csdn.net/qq_39924622/article/details/107368933