这篇文章总结了一下这两天刷的二叉树的解题方法，主要是递归、迭代的DFS、迭代的BSF这三种。题目列表如下：
题目列表
101 二叉树的最大深度
111 二叉树的最小深度
110 平衡二叉树
108 将有序数组转换为二叉搜索树
112 路径总和
226 翻转二叉树
257 二叉树的所有路径
235 二叉搜索树的最近公共祖先
404 左叶子之和
101 二叉树的最大深度
题目大意
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，返回它的最大深度3。
解法一：递归
思考递归解法时，想清楚三个问题：
1.返回条件是什么？
答：在此题中，如果根节点是个空结点，返回高度0。
2.递归返回的是什么？
答：返回树的高度。
直接来看看递归程序。
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
解法二：DFS
DFS需要借助栈来实现，这里我们设置两个栈，一个操作结点，一个记录每个结点的层数。每当我们将一个结点的左右孩子入栈，其左右孩子的层数就会在父节点层数的基础上加一。
public static int maxDepth(TreeNode root) {
if(root==null) return 0;
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> value = new Stack<>(); //保存层数
stack.push(root); //根节点加入stack
value.push(1);
int depth = 1;
while(!stack.isEmpty()) {
TreeNode p = stack.pop();
int cur= value.pop(); //当前结点的层数
depth = depth>cur?depth:cur;
if(p.left!=null) {
stack.push(p.left);
value.push(cur+1);
}
if(p.right!=null) {
stack.push(p.right);
value.push(cur+1);
}
}
return depth;
}
解法三：BFS
广度优先搜索借助队列完成，它可以实现层次遍历。每次弹出一个元素，就要将它的左右孩子入队。直至队列为空。
public static int maxDepth(TreeNode root) {
if(root==null) return 0;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
int depth = 0;
while(!que.isEmpty()) {
int size = que.size(); //上一层遗留了多少结点
++depth;
for(int i=0;i<size;++i) { //将上一层的结点全部出队
TreeNode node = que.poll();
if(node.left!=null) //左节点入队
que.offer(node.left);
if(node.right!=null) //右节点入队
que.offer(node.right);
}
}
return depth;
}
111 二叉树的最小深度
题目大意
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，返回它的最小深度 2。
思路
这一题和求二叉树的高度类似，有递归、DFS、BFS三种常用解法。需要随时更新当前最小的depth。
解法一：递归
public int minDepth(TreeNode root) {
if(root==null) return 0;
if(root.left == null && root.right == null) return 1;
int cur_min_depth = Integer.MAX_VALUE;
if(root.left!=null) cur_min_depth = Math.min(minDepth(root.left),cur_min_depth);
if(root.right!=null) cur_min_depth = Math.min(minDepth(root.right),cur_min_depth);
return cur_min_depth+1;
}
运行时间1ms。
解法二：BFS
层次遍历，当访问到第一个叶子结点就可以结束算法，返回最小的高度。
public int minDepth(TreeNode root) {
if(root == null) return 0;
Queue <TreeNode> que = new LinkedList<>();
que.offer(root);
int ans = 0;
while(!que.isEmpty()) {
++ans; //这一层的层数
int size = que.size();
for(int i=0;i<size;i++) {
TreeNode p = que.poll();
if(p.left == null && p.right==null) //叶子结点
return ans;
if(p.left!=null) que.offer(p.left);
if(p.right!=null) que.offer(p.right);
}
}
return ans;
}
运行时间1ms。
解法三：DFS
依旧用两个栈，一个记录结点，一个记录层数，还有一个min_depth变量，随时更新当前最小的层数。
public int minDepth(TreeNode root) {
if(root == null) return 0;
Stack <TreeNode> stack = new Stack<>();
Stack <Integer> value = new Stack<>();
stack.push(root);
value.push(1);
int min_depth = Integer.MAX_VALUE;
while(!stack.isEmpty()) {
TreeNode p = stack.pop();
int temp = value.pop();
if(p.left == null && p.right == null) min_depth= Math.min(temp,min_depth);
if(p.left!=null) {
stack.push(p.left);
value.push(temp+1);
}
if(p.right!=null) {
stack.push(p.right);
value.push(temp+1);
}
}
return min_depth;
}
解法四
这个解法将单支树的情况做了特殊考虑。
public static int minDepth(TreeNode root) {
//1.根节点为空
if(root==null) return 0;
//2.根节点左右孩子为空
if(root.left==null && root.right==null) return 1;
int left = minDepth(root.left);
int right = minDepth(root.right);
//3.单枝树
if(root.left==null || root.right==null) return left+right+1;
//4.非单枝树
return Math.min(left,right)+1;
}
110 平衡二叉树
题目大意
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例：
给定二叉树 [3,9,20,null,null,15,7]，返回 true 。
解法一：递归(自顶向下)
判断一棵树是否平衡的流程为，首先根节点平衡吗？若平衡，判断它的左、右子树是否都平衡。算法应该包含一个求子树高度的函数height。
private int height(TreeNode root) {
if(root == null) return 0;
return Math.max(height(root.left),height(root.right))+1;
}
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return isBalanced(root.left) && isBalanced(root.right) &&
(Math.abs(height(root.left)-height(root.right))<=1);
}
运行时间3ms。
解法二：自底向上，递归。
在求子树高度时，如果发现任何一棵子树打破了平衡，马上返回-1终止算法。
public boolean isBalanced(TreeNode root) {
int res = height(root); //求树所有叶子的高度
return res==-1?false:true;
}
private int height(TreeNode root) {
if(root == null) return 0;
int heightOfLeft = height(root.left);
if(heightOfLeft == -1) return -1;
int heightOfRight = height(root.right);
if(heightOfRight == -1) return -1;
if(Math.abs(heightOfLeft-heightOfRight)>1) return -1;
return Math.max(heightOfLeft,heightOfRight)+1;
}
运行时间3ms。
解法三：设置全局变量
很好理解，直接看代码吧。
public boolean isBalanced(TreeNode root) {
height(root); //求树所有叶子的高度
return res;
}
boolean res = true;
private int height(TreeNode root) {
if(root == null ||!res) return 0;
int left = height(root.left);
int right = height(root.right);
if(Math.abs(left-right)>1) res = false;
return Math.max(left,right)+1;
}
运行时间2ms。
108 将有序数组转换为二叉搜索树
题目大意
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例：
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
思路
因为给出的数组有序，此题类似于二分法解法，每次取中间的数mid作为根节点，小于mid的部分划分为左子树，大于mid的部分划分为右子树。
public TreeNode sortedArrayToBST(int[] nums) {
return createBST(nums,0,nums.length-1);
}
public TreeNode createBST(int[] nums,int low,int high) {
if(low>high) return null; //注意递归的结束条件(low>high)
int mid = (low+high) >>>1;
TreeNode root = new TreeNode(nums[mid]);
root.left = createBST(nums,low,mid-1);
root.right = createBST(nums,mid+1,high);
return root;
}
112 路径总和
题目大意
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例：
给定如下二叉树，以及目标和 sum = 22，返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
解法一：递归
这一版是自己写的递归程序，写的比较繁琐，但是理解上应该没问题。之后会贴上优化后的版本。
public boolean hasPathSum(TreeNode root, int sum) {
findPath(root,sum);
return flag;
}
private boolean findPath(TreeNode root, int sum) {
if(root == null) return false;
if(root.val == sum && root.left == null && root.right == null) {
flag = true;
return true;
}
if(root.left!=null) findPath(root.left,sum-root.val);
if(flag) return true;
if(root.right!=null) findPath(root.right,sum-root.val);
if(flag) return true;
return false;
}
未优化版本，运行时间2ms。接下来来看评论区的优化版本。
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null) return false;
sum -= root.val;
if(root.left==null && root.right==null) return sum==0;
return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);
}
解法二：DFS
利用两个栈，一个存储结点，一个存储剩余的路径长度。
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null) return false;
Stack<TreeNode> node = new Stack<>();
Stack<Integer> num = new Stack<>();
node.push(root);
num.push(sum-root.val); //剩余路径
while(!node.isEmpty()) {
TreeNode p = node.pop();
int path = num.pop();
if(path==0 && p.left==null && p.right==null) return true;
if(p.left!=null) {
node.push(p.left);
num.push(path-p.left.val);
}
if(p.right!=null) {
node.push(p.right);
num.push(path-p.right.val);
}
}
return false;
}
226 翻转二叉树
题目大意
翻转一棵二叉树。
示例:
输入：
输出：
方法一：递归
递归结束的条件为该节点为null或者该节点的左右孩子为空。
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
if(root.left==null && root.right == null) return root;
root.left = invertTree(root.left);
root.right = invertTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root;
}
运行时间1ms,击败89.13%。
方法二：迭代
利用层序遍历，交换每一个节点的左右节点。当poll的时候，进行交换操作。
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()) {
TreeNode cur = que.poll();
TreeNode temp = cur.left;
cur.left = cur.right;
cur.right = temp;
if(cur.left!=null) que.offer(cur.left);
if(cur.right!=null) que.offer(cur.right);
}
return root;
}
运行时间1ms,击败89.09%。
257 二叉树的所有路径
题目大意
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例：
方法一：递归
题目给出的函数返回List,在遍历树的时候，需要利用String path存储路径，遍历时采用先序遍历的方式，每次访问一个结点，就将它拼接到path字符串中。当该结点没有左右孩子的时候，一条完整path生成，将它加入list中。
public List<String> binaryTreePaths(TreeNode root) {
List<String> list = new ArrayList<>();
if(root==null) return list;
findPath(root,list,"");
return list;
}
private void findPath(TreeNode root,List list,String path) {
path += root.val+" ";
if(root.left==null && root.right==null) {
list.add(path.trim().replace(" ","->"));
}
if(root.left!=null)
findPath(root.left,list,path);
if(root.right!=null)
findPath(root.right,list,path);
}
运行时间14ms,击败6.7%。
方法二：迭代
迭代方法中利用两个栈结构，一个存储遍历的node，另一个存储path。直接通过代码理解。
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new LinkedList<>();
if(root==null) return res;
LinkedList<TreeNode> nodes = new LinkedList<>();
LinkedList<String> paths = new LinkedList<>();
nodes.add(root);
paths.add(Integer.toString(root.val));
TreeNode node;
String path;
while(!nodes.isEmpty()) {
node = nodes.pollLast();
path = paths.pollLast();
if(node.left==null && node.right == null)
res.add(path);
if(node.left!=null) {
nodes.add(node.left);
paths.add(path+"->"+Integer.toString(node.left.val));
}
if(node.right!=null) {
nodes.add(node.right);
paths.add(path+"->"+Integer.toString(node.right.val));
}
}
return res;
}
}
运行时间3ms,击败91.68%。
235 二叉搜索树的最近公共祖先
题目大意
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 为不同节点且均存在于给定的二叉搜索树中。
方法一：递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
if(root.val>p.val && root.val > q.val)
return lowestCommonAncestor(root.left,p,q);
else if(root.val<p.val && root.val<q.val)
return lowestCommonAncestor(root.right,p,q);
return root;
}
运行时间11ms，击败72.19%。
方法二：迭代
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
while(root!=null) {
if(root.val>p.val && root.val > q.val)
root = root.left;
else if(root.val < q.val && root.val < p.val)
root = root.right;
else
return root;
}
return root;
}
运行时间12ms,击败37.02%。
404 左叶子之和
题目大意
计算给定二叉树的所有左叶子之和。
示例：
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
方法一：栈
利用栈，遍历整个二叉树，并且对每个结点判断是否为左叶子。
public int sumOfLeftLeaves(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if (root==null) return 0;
int res = 0;
stack.push(root);
while(!stack.isEmpty()) {
TreeNode t = stack.pop();
if(t.left!=null) stack.push(t.left);
if(t.right!=null) stack.push(t.right);
if(t.left!=null && t.left.left==null && t.left.right==null) res+=t.left.val;
}
return res;
}
运行时间2ms，击败15.56%。
方法二：递归
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return 0;
if(root.left!=null && root.left.left==null && root.left.right==null)
return root.left.val + sumOfLeftLeaves(root.right);
return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right);
}
运行时间0ms,击败100%。
