二叉树专题
- 前言
- 一 . 使用递归和非递归实现二叉树的遍历
- 二. 二叉树的相关概念及实现判断
- 三. [给定两个二叉树的节点p和q，找到他们的最近公共祖先节点](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
- 四. [在二叉算树中找到一个节点的后继节点](https://www.nowcoder.com/practice/c37ec6a9e4084b9c943be2d3a369e177?tpId=101&&tqId=33243&rp=1&ru=/ta/programmer-code-interview-guide&qru=/ta/programmer-code-interview-guide/question-ranking)
- 五. [二叉树的序列化和反序列化](https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/)
- 六. [折纸问题](https://www.nowcoder.com/practice/e0e3459723e04a64900a2ec53bdf8852?tpId=101&&tqId=33128&rp=1&ru=/ta/programmer-code-interview-guide&qru=/ta/programmer-code-interview-guide/question-ranking)
前言
点击题目就可以跳转到leetcode或者牛客进练习。
一 . 使用递归和非递归实现二叉树的遍历
1.1.递归实现先序遍历，中续遍历，后序遍历
递归实现相对简单，直接上代码；
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
//递归实现先序遍历
public void pre(TreeNode root,List<Integer> list){
if(root == null) return;
list.add(root.val);//根
pre(root.left,list);//左
pre(root.right,list);//右
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
pre(root,list);
return list;
}
//递归实现中序遍历
public void mid(TreeNode root,List<Integer> list){
if(root == null) return;
mid(root.left,list);//左
list.add(root.val);//根
mid(root.right,list);//右
}
public List<Integer> midorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
mid(root,list);
return list;
}
//递归实现后续遍历
public void post(TreeNode root,List<Integer> list){
if(root == null) return;
post(root.left,list);//左
post(root.right,list);//右
list.add(root.val);//根
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
post(root,list);
return list;
}
}
1.2.非递归实现先序遍历，中序遍历，后续遍历
1.2.1 非递归实现先序遍历：
1.前序遍历是跟左右，先把root放入栈中；
2.将栈中元素弹出，并将该元素其按照右孩子，左孩子（如果有的话）的顺序压入栈中；
3.重复操作 2 。
class Solution {
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null) stack.push(root);//操作1
while(!stack.isEmpty()){//操作2
root = stack.pop();
list.add(root.val);
if(root.right != null){
stack.push(root.right);
}
if(root.left != null){
stack.push(root.left);
}
}
return list;
}
}
1.2.2 非递归实现后序遍历
后续遍历是左右根，前序遍历是根左右，只需把前序遍历的代码修改一下变为根右左放入栈中，再输出就得到了后序遍历。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> help = new Stack<>();
if(root != null) stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
help.push(root);
if(root.left != null) stack.push(root.left);
if(root.right != null) stack.push(root.right);
}
while(!help.isEmpty()){
list.add(help.pop().val);
}
return list;
}
}
1.2.3 非递归实现中序遍历
1.中序遍历是左跟右，所以我们先一直遍历根节点的左孩子直到为空，并依次压入栈中，并进入操作 2；
2.然后接下来弹出栈顶元素，如果其有右孩子，则将右孩子压入栈中，并重复操作 1。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()){
if(root != null){//操作1
stack.push(root);
root = root.left;
}else{//操作2
root = stack.pop();
list.add(root.val);
root = root.right;
}
}
return list;
}
}
二. 二叉树的相关概念及实现判断
2.1 判断二叉树是否为搜索二叉树
思路相对好想，只要保证root满足以下两条就是BFT：
1.root的所有的左子树都是BFT且所有的右子树都是BFT
2.root的所有左子树中的最大值小于root的值且root的所有右子树的最 小值大于root的值；
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public boolean isBST(TreeNode root,Integer min,Integer max){
if(root == null) return true;
int val = root.val;
//保证root的左子树的最大值小于root的值，root右子树的最小值大于root的值；
if(min != null && min >= val) return false;
if(max != null && max <= val) return false;
//保证root的左子树是BFT，root的右子树是BFT
if(!isBST(root.left,min,val)) return false;
if(!isBST(root.right,val,max)) return false;
return true;
}
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
return isBST(root,null,null);
}
}
2.2 判断二叉树是否为完全二叉树
使用宽度优先进行遍历，遍历过程中出现如下情况就不是完全二叉树：
1.遇到左右孩子不为空的节点并且该节点不是叶子节点；
2.遇到节点的左孩子为空且右孩子不为空的时候；
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public boolean isCompleteTree(TreeNode root) {
if(root == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean isMeet = false;//表示是否遇到左右孩子不双全的节点
TreeNode l = null;
TreeNode r = null;
while(!queue.isEmpty()){
root = queue.poll();
l = root.left;
r = root.right;
if(
//遇到左右孩子不双全并且不是叶子节点的节点的时候，不是完全二叉树
(isMeet && (l != null || r != null))
||
//遇到左孩子为空且右孩子不为空的节点的时候，不是完全二叉树
(l == null && r != null)){
return false;
}
if(l != null) queue.add(l);
if(r != null) queue.add(r);
if(l == null || r == null) isMeet = true;
}
return true;
}
}
2.3 判断二叉树是否为满二叉树
只要保证节点的个数nodes和二叉树的高度height满足nodes = 2的height次方 - 1就是满二叉树；
public class IsFull {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static boolean isFull1(Node head) {
if (head == null) {
return true;
}
int height = h(head);
int nodes = n(head);
return (1 << height) - 1 == nodes;//位运算速度快
}
//求深度height
public static int h(Node head) {
if (head == null) {
return 0;
}
return Math.max(h(head.left), h(head.right)) + 1;
}
//求节点个数nodes
public static int n(Node head) {
if (head == null) {
return 0;
}
return n(head.left) + n(head.right) + 1;
}
}
2.4 求一颗二叉树的最大宽度
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public int maxWidth(TreeNode root) {
int max = 0;
Queue<TreeNode> queue = new LinkedList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()){
int n = queue.size();
for(int i = 0;i < n;i++){
root = queue.poll();
if(root.left != null) queue.add(root.left);
if(root.right != null) queue.add(root.right);
}
max = Math.max(max，n);
}
return max;
}
}
2.5 判断二叉树是否为平衡二叉树
满足左右子树高度不大于1的二叉树为平衡二叉树；
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public int help(TreeNode root){
if(root == null) return -1;
int left = help(root.left);
int right = help(root.right);
return 1 + Math.max(left,right);
}
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
if(Math.abs(help(root.left) - help(root.right)) > 1) return false;
return isBalanced(root.left) && isBalanced(root.right);
}
}
三. 给定两个二叉树的节点p和q，找到他们的最近公共祖先节点
节点的子树中是否含有p和q，以及该节点是不是最低公共子树；
/** * 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;//当遍历到底或者遍历到p或q时向上返回root；
TreeNode left = lowestCommonAncestor(root.left,p,q);//在左子树中寻找p或q
TreeNode right = lowestCommonAncestor(root.right,p,q);//在右子树中寻找p或q
if(left != null && right != null) return root;//此时证明p和q在分别在该节点的左右子树中；
return left != null ? left : right;//如果left不为空，证明左子树中含有p或q，否则右子树中含有p或q；
}
}
四. 在二叉算树中找到一个节点的后继节点
public class SuccessorNode {
public static class Node {
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int data) {
this.value = data;
}
}
public static Node getSuccessorNode(Node node) {
if (node == null) {
return node;
}
if (node.right != null) {
return getLeftMost(node.right);
} else { // 无右子树
Node parent = node.parent;
while (parent != null && parent.right == node) { // 当前节点是其父亲节点右孩子
node = parent;
parent = node.parent;
}
return parent;
}
}
public static Node getLeftMost(Node node) {
if (node == null) {
return node;
}
while (node.left != null) {
node = node.left;
}
return node;
}
五. 二叉树的序列化和反序列化
1.按照先序遍历的方式去进行序列化，每遍历一个节点在后面加上""，就会自动转为String，如果遇到节点的左右孩
子有为空的话，就记为"#";
2. 反序列化的时候，先将之前序列化得到的String按照"_",分隔开存入数组中，如果元素为"#"则返回空加下来再将数
组中的元素一次放入队列中，接下来按照先序遍历的顺序（即跟左右）来递归进而得到反序列化的结果。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null) return "#_";
String res = root.val + "_";//跟
res += serialize(root.left);//左
res += serialize(root.right);//右
return res;
}
// Decodes your encoded data to tree.
public TreeNode desHelp(Queue<String> queue){//按照先序遍历的顺序去进行递归
String value = queue.poll();
if(value.equals("#")) return null;
TreeNode root = new TreeNode(Integer.valueOf(value));//根
root.left = desHelp(queue);//左
root.right = desHelp(queue);//右
return root;
}
public TreeNode deserialize(String data) {
String[] values = data.split("_");//将data按照"_"进行分割并存入数组中
Queue<String> queue = new LinkedList<>();
for(int i =0 ; i != values.length ; i++){
queue.offer(values[i]);//将数组中的元素放入队列中，方便接下来的递鬼
}
return desHelp(queue);
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
六. 折纸问题
public class Code10_PaperFolding {
public static void printAllFolds(int N) {
printProcess(1, N, true);
}
public static void printProcess(int i, int N, boolean down) {
if (i > N) {
return;
}
printProcess(i + 1, N, true);
System.out.println(down ? "down " : "up ");
printProcess(i + 1, N, false);
}
public static void main(String[] args) {
int N = 1;
printAllFolds(N);
}
}
京公网安备 11010502036488号