二叉树专题

二叉树专题前言一 . 使用递归和非递归实现二叉树的遍历1.1.递归实现先序遍历,中续遍历,后序遍历1.2.非递归实现先序遍历,中序遍历,后续遍历1.2.1 [非递归实现先序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/):1.2.2 [非递归实现后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)1.2.3 [非递归实现中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)二. 二叉树的相关概念及实现判断2.1 [判断二叉树是否为搜索二叉树](https://leetcode-cn.com/problems/validate-binary-search-tree/)2.2 [判断二叉树是否为完全二叉树](https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree/)2.3 判断二叉树是否为满二叉树2.4 求一颗二叉树的最大宽度2.5 [判断二叉树是否为平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree/)三. [给定两个二叉树的节点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);
}
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

二叉树专题

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 二叉树专题
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏