二叉树
本篇文章记录常见的二叉树算法题
leetcode94 二叉树的中序遍历
/**
* 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<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(!stack.isEmpty() || cur!=null){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}
}
这是二叉树的最经典问题之一,BST的相关问题可以沿用该思路
leetcode104 二叉树的最大深度
/**
* 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) {
if(root == null){
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left,right)+1;
}
}
二叉树大部分题目可以考虑使用递归,这题是一个简单案例
leetcode236 二叉树的最近公共祖先
/**
* 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 left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left!=null &&right!=null){
return root;
}
if(left!=null){
return left;
}
return right;
}
}
这个题也是递归的使用
leetcode102 二叉树的层序遍历
/**
* 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>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null){
return res;
}
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> temp = new ArrayList<>();
int size = queue.size();
/** 表示一层 */
for(int i = 0;i<size;i++){
TreeNode node = queue.poll();
temp.add(node.val);
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
res.add(temp);
}
return res;
}
}
这题目也是比较经典的题,类似求树的深度,右视图等都可以使用该思路
leetcode105 从前序与中序遍历序列构造二叉树
/**
* 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 TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length == 0||inorder.length == 0){
return null;
}
TreeNode root = new TreeNode(preorder[0]);
for(int i=0;i<preorder.length;i++){
if(inorder[i] == preorder[0]){
root.left = buildTree(Arrays.copyOfRange(preorder,1,1+i),Arrays.copyOfRange(inorder,0,i));
root.right = buildTree(Arrays.copyOfRange(preorder,1+i,preorder.length),Arrays.copyOfRange(inorder,i+1,inorder.length));
break;
}
}
return root;
}
}