二叉树
二叉树的数据结构
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}
二叉树的递归遍历
前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
// 递归
preOrder(root,list);
return list;
}
public void preOrder(TreeNode root,List<Integer> list){
// 1. 终止条件
if(root == null) return;
// 2. 单层逻辑
list.add(root.val);
preOrder(root.left,list);
preOrder(root.right,list);
}
}
后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
postOrder(root,list);
return list;
}
public void postOrder(TreeNode root,List<Integer> list){
if(root == null) return;
postOrder(root.left,list);
postOrder(root.right,list);
list.add(root.val);
}
}
中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
inOrder(root,list);
return list;
}
public void inOrder(TreeNode root,List<Integer> list){
if(root == null) return ;
inOrder(root.left,list);
list.add(root.val);
inOrder(root.right,list);
}
}
二叉树的迭代遍历
前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.empty()){
TreeNode node = stack.pop();
list.add(node.val);
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
return list;
}
}
中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
while(stack.size()>0 || root!=null) {
//不断往左子树方向走，每走一次就将当前节点保存到栈中
//这是模拟递归的调用
if(root!=null) {
stack.add(root);
root = root.left;
//当前节点为空，说明左边走到头了，从栈中弹出节点并保存
//然后转向右边节点，继续上面整个过程
} else {
TreeNode tmp = stack.pop();
res.add(tmp.val);
root = tmp.right;
}
}
return res;
}
}
后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
//使用迭代遍历
List<Integer> result = new ArrayList<>();
if(root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.empty()){
TreeNode node = stack.pop();
result.add(node.val);
if(node.left!=null){
stack.push(node.left);
}
if(node.right!=null){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
}
层序遍历
// 这是层序遍历的迭代法
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root == null) return res;
// 添加元素，用offer ,add其实也行
que.offer(root);
while(!que.isEmpty()){
List<Integer> list = new ArrayList<>();
int len = que.size();
while(len>0){
// 移除元素，用poll ，或者remove也可以
TreeNode temp = que.poll();
if(temp.left!=null) que.offer(temp.left);
if(temp.right!=null) que.offer(temp.right);
list.add(temp.val);
len--;
}
res.add(list);
}
return res;
}
}
深度优先遍历（DFS）
深度优先算法的求解过程，都可以把它画成树的形式，并且对这颗树的DFS求解过程其实就是对这棵树的先序遍历过程。
广度优先搜索（BFS）
对于BFS求解过程，都可以转换成树的层序遍历问题。
翻转二叉树
二叉树的翻转用递归去做是比较简单的，记这一个模板就行了。
class Solution {
public TreeNode invertTree(TreeNode root) {
// 对每一个节点都进行翻转就可以
// 叶子节点就返回
if(root == null) return root;
// 处理每次交换
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
对称二叉树
这个二叉树的题目做了好几遍了，每次都写不好。
class Solution {
public boolean isSymmetric(TreeNode root) {
return root==null?true: recur(root.left,root.right);
}
boolean recur(TreeNode L,TreeNode R){
if(L==null && R==null) return true;
if(L==null || R == null || L.val!=R.val) return false;
return recur(L.left,R.right) && recur(R.left,L.right);
}
}
二叉树的最大深度
class Solution {
public int maxDepth(TreeNode root) {
// 节点为空，高度为 0
if(root == null){
return 0;
}
// 递归计算左子树的最大深度
int leftHeight = maxDepth(root.left);
// 递归计算右子树的最大深度
int rightHeight = maxDepth(root.right);
// 二叉树的最大深度 = 子树的最大深度 + 1（1 是根节点）
return Math.max(leftHeight, rightHeight) + 1;
}
}
二叉树的最小深度
最小深度这个题还和最大深度不一样，需要分情况讨论。
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
// 对于重复子问题需要分情况讨论
int leftHeight=0,rightHeight=0;
if(root.left==null && root.right==null){
return 1;
}
leftHeight = minDepth(root.left);
rightHeight = minDepth(root.right);
if(root.left!=null && root.right==null){
return leftHeight+1;
}
if(root.left==null && root.right!=null){
return rightHeight+1;
}
return Math.min(leftHeight,rightHeight)+1;
}
}
平衡二叉树
这样是求每一个节点的左右子树的深度，进行了两轮递归，自顶向下。时间复杂度较高。
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null ) return true;
// 我可不可以传左右节点的高度进行递归比较
int LH = maxHeight(root.left);
int RH = maxHeight(root.right);
return Math.abs(LH-RH)<=1 && isBalanced(root.left) && isBalanced(root.right) ;
}
// 写一个函数求树最大深度
int maxHeight(TreeNode root){
if(root == null) return 0;
int leftHeight = maxHeight(root.left);
int rightHeight = maxHeight(root.right);
return Math.max(leftHeight,rightHeight)+1;
}
}
正常的话，这道题应该自底向上。
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >=0;
}
public int height(TreeNode root){
if(root == null) return 0;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if(leftHeight==-1 || rightHeight == -1 || Math.abs(leftHeight-rightHeight)>1){
return -1;
}else{
return Math.max(leftHeight,rightHeight)+1;
}
}
}
左叶子之和
这个题目的巧妙之处在于，设置了一个isLeft变量。
class Solution {
int sum = 0;
public int sumOfLeftLeaves(TreeNode root) {
// 只计算左叶子的和
preOrder(root,false);
return sum;
}
void preOrder(TreeNode root,boolean isLeft){
if(root == null) return;
if(root.left== null && root.right == null && isLeft){
sum+=root.val;
return;
}
preOrder(root.left,true);
preOrder(root.right,false);
}
}
若有收获，就点个赞吧
0 人点赞
