三、二叉树-算法总结

文章目录

三、二叉树
- 3.1 二叉树遍历
- - 3.1.1 前序遍历
  - 3.1.2 中序遍历
  - 3.1.3 后序遍历
  - 3.1.4 DFS 深度搜索
  - 3.1.5 BFS 广度搜索
  - 3.1.6 BFS 广度搜索 2
- 3.2 二叉树分治
- - 3.2.1 检验二叉搜索树
  - 3.2.2 二叉树的最大深度
  - 3.2.3 平衡二叉树
- 3.3 二叉树分治法
- - 3.3.1 二叉树中的最大路径和
  - 3.3.2 二叉树的最近的公共祖先

三、二叉树

3.1 二叉树遍历

3.1.1 前序遍历

144. 二叉树的前序遍历
在这里插入图片描述

/*** Definition for a binary tree node.* public 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;*     }* }*//**method1: 基于递归的先序遍历*/
// class Solution {
//     private List<Integer> nums = new ArrayList<>();
//     public List<Integer> preorderTraversal(TreeNode root) {
//         preIter(root);
//         return nums;
//     }//     private void preIter(TreeNode node){
//         if(node == null){
//             return;
//         }
//         nums.add(node.val);
//         preIter(node.left);
//         preIter(node.right);
//     }// }/**
method2: 基于stack的非递归先序遍历*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode p = root;while(p != null || !stack.isEmpty()){// 依次定位左边的子树,直至最左侧的子节点while(p!=null){list.add(p.val);stack.push(p);p = p.left;}// 出栈定位结点的右子树if(!stack.isEmpty()){p = stack.pop();p = p.right;}}return list;}
}

3.1.2 中序遍历

94. 二叉树的中序遍历
在这里插入图片描述

/*** Definition for a binary tree node.* public 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;*     }* }*//**method1: 基于递归的中序遍历*/
// class Solution {
//     private List<Integer> nums = new ArrayList<>();
//     public List<Integer> inorderTraversal(TreeNode root) {
//         midIter(root);
//         return nums;
//     }//     private void midIter(TreeNode node){
//         if(node == null){
//             return;
//         }
//         preIter(node.left);
//         nums.add(node.val);
//         preIter(node.right);
//     }// }/**
method2：基于stack的非递归中序遍历*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode p = root;while(p != null || !stack.isEmpty()){while(p != null){stack.push(p);p = p.left;}if(!stack.isEmpty()){p = stack.pop();list.add(p.val);p = p.right;}}return list;}}

3.1.3 后序遍历

145. 二叉树的后序遍历
在这里插入图片描述

/*** Definition for a binary tree node.* public 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;*     }* }*//**method1: 基于递归的后序遍历*/
// class Solution {
//     private List<Integer> nums = new ArrayList<>();//     public List<Integer> postorderTraversal(TreeNode root) {
//         postOrder(root);
//         return nums;
//     }//     private void postOrder(TreeNode node){
//         if(node == null){
//             return;
//         }
//         postOrder(node.left);
//         postOrder(node.right);
//         nums.add(node.val);
//     }
// }/**method2: 基于stack的非递归后序遍历*/
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode p = root;// 通过lastVisit标识右子节点是否已经弹出TreeNode lastVisit = root;while (p != null || !stack.isEmpty()) {while (p != null) {stack.push(p);p = p.left;}//查看当前栈顶元素p = stack.peek();//如果其右子树也为空，或者右子树已经访问，则可以访问if (p.right == null || p.right == lastVisit) {result.add(p.val);stack.pop();// 标记当前这个节点已经弹出过lastVisit = p;p = null;} else {//否则继续遍历右子树p = p.right;}}return result;
}}

3.1.4 DFS 深度搜索

257. 二叉树的所有路径
在这里插入图片描述

/*** Definition for a binary tree node.* public 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<String> binaryTreePaths(TreeNode root) {List<String> paths = new ArrayList<>();dfs(root, new StringBuffer(), paths);return paths;}private void dfs(TreeNode node,StringBuffer path,List<String> paths){if(node == null){return;}path.append(node.val);// 当前结点是叶子结点时，将路径信息加入集合if(node.left == null && node.right == null){paths.add(path.toString());return;}path.append("->");// 当前是非叶子结点dfs(node.left,new StringBuffer(path),paths);dfs(node.right,new StringBuffer(path),paths);}
}

3.1.5 BFS 广度搜索

102. 二叉树的层序遍历
在这里插入图片描述

/*** Definition for a binary tree node.* public 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 {// method：借用队列完成层次遍历public List<List<Integer>> levelOrder(TreeNode root) {if (root == null) {return new ArrayList<>();}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);TreeNode node;int n;List<List<Integer>> result = new ArrayList<>();List<Integer> layerOrder;while (!queue.isEmpty()) {// 某一层的结点个数n = queue.size();layerOrder = new ArrayList<>();for(int i = 0 ;i<n;i++){node = queue.poll();layerOrder.add(node.val);if(node.left != null){queue.add(node.left);}if(node.right != null){queue.add(node.right);}}result.add(layerOrder);}return result;}
}

3.1.6 BFS 广度搜索 2

107. 二叉树的层序遍历 II
在这里插入图片描述

/*** Definition for a binary tree node.* public 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<List<Integer>> levelOrderBottom(TreeNode root) {if(root == null){return new ArrayList<>();}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);TreeNode p;int n;List<List<Integer>> result = new ArrayList<>();List<Integer> layerOrder;while(!queue.isEmpty()){n = queue.size();layerOrder = new ArrayList<>();for(int i = 0;i<n;i++){p = queue.poll();layerOrder.add(p.val);if(p.left != null){queue.add(p.left);}if(p.right != null){queue.add(p.right);}}result.add(layerOrder);}Collections.reverse(result); // 反转return result;}
}

3.2 二叉树分治

先分别处理局部，在合并结果
分支模板

递归返回条件
分段处理
合并结果

public ResultType traversal(TreeNode root) {// null or leafif (root == null) {// do something and return}// DivideResultType left = traversal(root.Left)ResultType right = traversal(root.Right)// ConquerResultType result = Merge from left and rightreturn result
}

3.2.1 检验二叉搜索树

98. 验证二叉搜索树
在这里插入图片描述

/*** Definition for a binary tree node.* public 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 {// method1: 基于中序遍历查找是否逆序// 时间复杂度 O(n)// 空间复杂度 O(n)// public boolean isValidBST(TreeNode root) {//     List<Integer> list = new ArrayList<>();//     midOrder(root,list);//     for(int i = 0;i<list.size()-1;i++){//         if(list.get(i) >= list.get(i+1)){//             return false;//         }//     }//     return true;// }// private void midOrder(TreeNode node,List<Integer> list){//     if(node == null){   //         return;//     }//     midOrder(node.left,list);//     list.add(node.val);//     midOrder(node.right,list);// }// method: 基于自顶向下遍历的判断方法// 时间复杂度：O(n)// 空间复杂度：O(H) 树的高度 public boolean isValidBST(TreeNode root) {return isValid(root,Long.MIN_VALUE,Long.MAX_VALUE);}private boolean isValid(TreeNode node,long min,long max){if(node == null){return true;}// 以当前结点作为子节点,比对它与其父节点的大小关系if(node.val <= min || node.val >= max){return false;}boolean left = isValid(node.left,min,node.val);boolean right = isValid(node.right,node.val,max);return left&&right;}}

3.2.2 二叉树的最大深度

104. 二叉树的最大深度
在这里插入图片描述

/*** Definition for a binary tree node.* public 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 int maxDepth(TreeNode root) {return height(root);}private int height(TreeNode node){if(node == null){return 0;}return Math.max(height(node.left),height(node.right)) + 1;}
}

3.2.3 平衡二叉树

110. 平衡二叉树
在这里插入图片描述

/*** Definition for a binary tree node.* public 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 boolean isBalanced(TreeNode root) {return maxDepth(root) >= 0;
}private int maxDepth(TreeNode p) {if (p == null) {return 0;}int left = maxDepth(p.left);int right = maxDepth(p.right);// 小于0代表存在非平衡子树（则依次向上传导）if (left < 0 || right < 0 || Math.abs(left - right) > 1) {return -1;} else {return Math.max(left, right) + 1;}
}
}

3.3 二叉树分治法

3.3.1 二叉树中的最大路径和

124. 二叉树中的最大路径和
在这里插入图片描述

/*** Definition for a binary tree node.* public 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 int maxPathSum(TreeNode root) {return maxPathDFS(root)[1];}// int[0]：表示子树（经过子树的根节点）的单边收益（设置下限为0）// int[1]：表示子树（经过子树的根节点）的内部最大路径和public int[] maxPathDFS(TreeNode node){// 叶子结点的"虚拟"子树返回if(node == null){return new int[]{0,Integer.MIN_VALUE};}// Divideint[] left = maxPathDFS(node.left);int[] right = maxPathDFS(node.right);int singleSum,bothSum;// Conquer// 获取经过当前树根节点的单边最大收益if(left[0] > right[0]){singleSum = Math.max(0,left[0]+node.val);}else{singleSum = Math.max(0,right[0]+node.val);}// 比较当前子树的内部路径和与其子树的内部路径bothSum = Math.max(left[1],right[1]);bothSum = Math.max(bothSum,left[0] + right[0] + node.val);return new int[]{singleSum,bothSum};}
}

3.3.2 二叉树的最近的公共祖先

236. 二叉树的最近公共祖先
在这里插入图片描述

/*** 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) {return lowestCom(root,p,q);}private TreeNode lowestCom(TreeNode node, TreeNode p, TreeNode q){if(node == null || node == p || node == q){return node;}TreeNode left = lowestCom(node.left, p, q);TreeNode right = lowestCom(node.right, p, q);if(left != null && right != null){return node;}return left != null ? left:right;}
}