二叉树和递归 文章目录 1.二叉树的最大深度 2.二叉树的最小深度 3.反转二叉树 4.相同的树 5.完全二叉树的节点个数 6.平衡二叉树判断 7.路径总和 8.路径总和II 9.路径总和III 10.求根到叶节点数字之和 11.二叉搜索树最近公共祖先 12.二叉树的最近公共祖先 13.二叉搜索树中第k小元素 14.删除二叉搜索树中的节点 15.将有序数组转为二叉搜索树 1.二叉树的最大深度 二叉树和递归 public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
} 2.二叉树的最小深度 二叉树和递归 /**
* 以root节点为根的二叉树的最小深度 = min(以root.left为根的二叉树的最小深度，以root.right为根的二叉树的最小深度) + 1（root节点）
* @param root
* @return
*/
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}else if(root.left != null && root.right != null){
return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
}else if(root.left != null){
return minDepth(root.left) + 1;
}else{
return minDepth(root.right) + 1;
}
} 3.反转二叉树 二叉树和递归 public TreeNode invertTree(TreeNode root) {
if(root == null)
return null;
invertTree(root.left);
invertTree(root.right);
TreeNode tmpLeft = root.left;
TreeNode tmpRight = root.right;
root.right = tmpLeft;
root.left = tmpRight;
return root;
} 4.相同的树 二叉树和递归 public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null)
return true;
if(p == null && q != null)
return false;
if(p != null && q == null)
return false;
if(p.val != q.val)
return false;
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
} 5.完全二叉树的节点个数 二叉树和递归 /**
* 二叉树节点数 = 左子树节点数 + 右子树节点数 + 当前节点
* @param root
* @return
*/
public int countNodes(TreeNode root) {
if(root == null)
return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
} 6.平衡二叉树判断 二叉树和递归 public boolean isBalanced(TreeNode root) {
if(root == null)
return true;
if(Math.abs(getHeight(root.left) - getHeight(root.right)) > 1)
return false;
else
return isBalanced(root.left) && isBalanced(root.right);
}
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
} else {
int lh = getHeight(root.left);
int rh = getHeight(root.right);
return Math.max(lh, rh) + 1;
}
} 7.路径总和 二叉树和递归 public boolean hasPathSum(TreeNode root, int sum) {
if(root == null)
return false;
if(root.left == null && root.right == null)
return root.val == sum;
if(hasPathSum(root.left,sum - root.val)){
return true;
}
if(hasPathSum(root.right,sum - root.val)){
return true;
}
return false;
} 8.路径总和II 二叉树和递归 public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<>();
if(root == null)
return res;
if(root.left == null && root.right == null && root.val == sum){
List<Integer> tmp = new ArrayList<>();
tmp.add(root.val);
res.add(tmp);
return res;
}
List<List<Integer>> leftList = pathSum(root.left,sum - root.val);
List<List<Integer>> rightList = pathSum(root.right,sum - root.val);
for(List<Integer> list : leftList){
list.add(0,root.val);
res.add(list);
}
for(List<Integer> list : rightList){
list.add(0,root.val);
res.add(list);
}
return res;
} 9.路径总和III 二叉树和递归 public int pathSum(TreeNode root, int sum) {
if(root == null)
return 0;
int res = findPath(root,sum);
res += pathSum(root.left,sum);
res += pathSum(root.right,sum);
return res;
}
public int findPath(TreeNode node,int sum){
if(node == null)
return 0;
int res = 0;
if(node.val == sum)
res += 1;
res += findPath(node.left,sum - node.val);
res += findPath(node.right,sum - node.val);
return res;
} 10.求根到叶节点数字之和 二叉树和递归 int sum = 0;
public int sumNumbers(TreeNode root) {
sumNumbers(0,root);
return sum;
}
private void sumNumbers(int i, TreeNode root) {
if(root == null)
return;
int k = 10 * i + root.val;
if(root.left == null && root.right == null)
sum += k;
sumNumbers(k,root.left);
sumNumbers(k,root.right);
} 11.二叉搜索树最近公共祖先 二叉树和递归 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return lca(root, p, q);
}
public TreeNode lca(TreeNode root, TreeNode p, TreeNode q){
if((root.val - p.val) * (root.val - q.val) <= 0){
return root;
}else if(root.val < p.val && root.val < q.val){
return lca(root.right,p,q);
}else{
return lca(root.left,p,q);
}
} 12.二叉树的最近公共祖先 二叉树和递归 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null)
return null;
if(root == q || root == p)
return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left != null && right != null)
return root;
else if(left != null)
return left;
else
return right;
} 13.二叉搜索树中第k小元素 <Integer> res = new ArrayList<>();
public int kthSmallest(TreeNode root, int k) {
dfs(root,res);
Collections.sort(res);
return res.get(k-1);
}
public void dfs(TreeNode root,List<Integer> list){
if(root == null){
return;
}
dfs(root.left,list);
list.add(root.val);
dfs(root.right,list);
} 14.删除二叉搜索树中的节点 public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key < root.val) {
// 待删除节点在左子树中
root.left = deleteNode(root.left, key);
return root;
} else if (key > root.val) {
// 待删除节点在右子树中
root.right = deleteNode(root.right, key);
return root;
} else {
// key == root.val，root 为待删除节点
if (root.left == null) {
// 返回右子树作为新的根
return root.right;
} else if (root.right == null) {
// 返回左子树作为新的根
return root.left;
} else {
// 左右子树都存在，返回后继节点（右子树最左叶子）作为新的根
TreeNode successor = min(root.right);
successor.right = deleteMin(root.right);
successor.left = root.left;
return successor;
}
}
}
private TreeNode min(TreeNode node) {
if (node.left == null) {
return node;
}
return min(node.left);
}
private TreeNode deleteMin(TreeNode node) {
if (node.left == null) {
return node.right;
}
node.left = deleteMin(node.left);
return node;
} 15.将有序数组转为二叉搜索树 public TreeNode sortedArrayToBST(int[] nums) {
if(nums==null)
return null;
return bst(nums,0,nums.length-1);
}
public TreeNode bst(int[] nums,int left,int right) {
if(left>right)
return null;
int mid = left + ((right-left)>>1);
TreeNode root = new TreeNode(nums[mid]);
root.left = bst(nums,left,mid-1);
root.right = bst(nums,mid+1,right);
return root;
} 
