• 算法拾遗十六二叉树相关算法

    算法拾遗十六二叉树相关

    二叉树递归序

    在这里插入图片描述
    整个过程发现每个字母都出现了三次，字母第一次出现的位置就是先序遍历，
    第二次出现的位置连一起就是中序，第三次出现的位置连在一起就是后序

    结论证明题

    在这里插入图片描述
    得到这颗树的先序遍历和后续遍历，求得先序遍历中X前面得所有节点，与
    后续遍历X后面得所有节点，得到【a,c】所以求得的节点是X的所有的祖先节点【只是x的祖先节点】，
    那么如何证明呢？
    1、首先证明x的所有的祖先节点一定在这样的交集里面
    由于先序遍历是头左右【所以先序遍历的所有祖先节点一定在X的左边】
    而后续遍历则是左右头那么X的祖先节点一定在X的后面
    2、为什么交集只有祖先节点？
    首先先序遍历X的孩子节点肯定不在X的前面（根左右，所有孩子节点都出现在X以右）【至少X的孩子
    不在交集中】
    X可以存在于树中节点有如下形式：
    在这里插入图片描述
    先看X作为左树情况下它的右兄弟会出现在X之后，不会出现在它的交集里面，
    那么X作为右树情况下它的先序遍历左兄弟会出现在X之前，那么后序遍历中是左右头
    ，X是在右里面，那么所有的左兄不会出现在X之后，右兄只会出现在X之后。
    那么求交集，就相当于去掉了左兄与右兄，只保留了祖先节点。

    非递归实现二叉树遍历

    先序遍历方式：
    1、先压入根节点，栈顶弹出记为cur
    在这里插入图片描述

    2、有右压入右，有左压入左，先右再左
    在这里插入图片描述
    然后再弹出b将e和d入栈，再弹出d，发现d没有左节点与右节点，再弹出e，发现e没有左节点与右节点，跳过，再弹出c，压入g与f,最后发现他们都没有子节点，依次弹出f和g。
    代码如下：

    	public static void pre(Node head) {
		System.out.print("pre-order: ");
		if (head != null) {
			Stack<Node> stack = new Stack<Node>();
			stack.add(head);
			while (!stack.isEmpty()) {
				head = stack.pop();
				System.out.print(head.value + " ");
				if (head.right != null) {
					stack.push(head.right);
				}
				if (head.left != null) {
					stack.push(head.left);
				}
			}
		}
		System.out.println();
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    后序遍历方式：
    则将上述方式（头左右）改成（头右左）的方式，就每次先压入左节点，再压入右节点，
    再弹出放入另一个栈里面去（最后就得到了左右头这个后序遍历）

    	public static void pos1(Node head) {
		System.out.print("pos-order: ");
		if (head != null) {
			Stack<Node> s1 = new Stack<Node>();
			Stack<Node> s2 = new Stack<Node>();
			s1.push(head);
			while (!s1.isEmpty()) {
				head = s1.pop(); // 头 右 左
				s2.push(head);
				if (head.left != null) {
					s1.push(head.left);
				}
				if (head.right != null) {
					s1.push(head.right);
				}
			}
			// 左 右 头
			while (!s2.isEmpty()) {
				System.out.print(s2.pop().value + " ");
			}
		}
		System.out.println();
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    中序遍历方式：
    在这里插入图片描述
    1、当前节点cur，cur为头的树，整条左边界进栈，直到遇到空（a,b,d依次入栈）
    2、栈中弹出节点打印，让这个节点的右孩子（让它为cur）重复第一个步骤
    3、栈为空停

    首先a,b,d依次入栈，然后弹出d，打印，再根据d重复第一个步骤，发现为空，然后
    栈中弹出b，重复第一个步骤，然后将e入栈，然后是空弹出e，然后再来到a节点，
    弹出a，找到它的右孩子重复步骤1，将f入栈，然后f重复步骤一，再重复步骤2，将f出战，
    然后再弹出c，找到它的右孩子g，再重复步骤1和2将g弹出来，最后整个栈空并且cur为空结束。

    	public static void in(Node cur) {
		System.out.print("in-order: ");
		if (cur != null) {
			Stack<Node> stack = new Stack<>();
			while (!stack.isEmpty() || cur != null) {
				if (cur != null) {
					stack.push(cur);
					cur = cur.left;
				} else {
					cur = stack.pop();
					System.out.print(cur.value + " ");
					cur = cur.right;
				}
			}
		}
		System.out.println();
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    并且如下图一样整棵树都可以通过左边界逐步分解掉的;
    在这里插入图片描述

    二叉树层序遍历（宽度优先遍历）

    方式：
    1、队列弹出一个cur，并且打印
    2、cur有左入左，有右入右
    重复步骤1、2直到队列为空为止

    	public static void level(Node head) {
		if (head == null) {
			return;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			System.out.println(cur.value);
			if (cur.left != null) {
				queue.add(cur.left);
			}
			if (cur.right != null) {
				queue.add(cur.right);
			}
		}
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    那么如何通过设置flag的方式来标记当前这一层已经结束了

    实现二叉树的序列化以及反序列化

    在这里插入图片描述
    以先序遍历为例，每遍历一个节点都用逗号分隔开，为null的时候采用#符号来标记，
    注意一定要用逗号分隔开每个节点，不然就会像上图中右边部分一样序列化出来一样的串，
    这样就没法区分了。
    如果用先序的方式序列化，那么就应该按照先序的方式反序列化。
    那么就先从0位置开始建立根节点，然后再建立左子树，直到第一个
    null为止，就开始建立它上一个节点的右子树。
    在这里插入图片描述
    就得出一个这样的形状：
    在这里插入图片描述
    然后再找它的左子树，以及右子树，都建完了以后回到根节点，建立根节点
    的右树。
    在这里插入图片描述
    这样一棵树序列化以及反序列化就成功了。
    代码如下【包含先序及后序遍历序列化，反序列化，以及层序遍历序列化】：

      /*
     * 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，
     * 以下代码全部实现了。
     * 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
     * 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
     * 比如如下两棵树
     *         __2
     *        /
     *       1
     *       和
     *       1__
     *          \
     *           2
     * 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
     *       
     * */
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Queue<String> preSerial(Node head) {
		Queue<String> ans = new LinkedList<>();
		pres(head, ans);
		return ans;
	}

	public static void pres(Node head, Queue<String> ans) {
		if (head == null) {
			ans.add(null);
		} else {
			ans.add(String.valueOf(head.value));
			pres(head.left, ans);
			pres(head.right, ans);
		}
	}

	public static Queue<String> inSerial(Node head) {
		Queue<String> ans = new LinkedList<>();
		ins(head, ans);
		return ans;
	}

	public static void ins(Node head, Queue<String> ans) {
		if (head == null) {
			ans.add(null);
		} else {
			ins(head.left, ans);
			ans.add(String.valueOf(head.value));
			ins(head.right, ans);
		}
	}

	public static Queue<String> posSerial(Node head) {
		Queue<String> ans = new LinkedList<>();
		poss(head, ans);
		return ans;
	}

	public static void poss(Node head, Queue<String> ans) {
		if (head == null) {
			ans.add(null);
		} else {
			poss(head.left, ans);
			poss(head.right, ans);
			ans.add(String.valueOf(head.value));
		}
	}

	public static Node buildByPreQueue(Queue<String> prelist) {
		if (prelist == null || prelist.size() == 0) {
			return null;
		}
		return preb(prelist);
	}

	public static Node preb(Queue<String> prelist) {
		String value = prelist.poll();
		if (value == null) {
			return null;
		}
		Node head = new Node(Integer.valueOf(value));
		//左子树右子树依次消费这个队列
		head.left = preb(prelist);
		head.right = preb(prelist);
		return head;
	}

	public static Node buildByPosQueue(Queue<String> poslist) {
		if (poslist == null || poslist.size() == 0) {
			return null;
		}
		// 左右中  ->  stack(中右左)
		Stack<String> stack = new Stack<>();
		while (!poslist.isEmpty()) {
			stack.push(poslist.poll());
		}
		return posb(stack);
	}

	public static Node posb(Stack<String> posstack) {
		String value = posstack.pop();
		if (value == null) {
			return null;
		}
		Node head = new Node(Integer.valueOf(value));
		head.right = posb(posstack);
		head.left = posb(posstack);
		return head;
	}

	public static Queue<String> levelSerial(Node head) {
		Queue<String> ans = new LinkedList<>();
		if (head == null) {
			ans.add(null);
		} else {
			ans.add(String.valueOf(head.value));
			Queue<Node> queue = new LinkedList<Node>();
			queue.add(head);//帮助我的按层遍历
			while (!queue.isEmpty()) {
				head = queue.poll(); // head 父   子
				if (head.left != null) {
					//左边不为空，进去就序列化并且也往队列里面放
					ans.add(String.valueOf(head.left.value));
					queue.add(head.left);
				} else {
					//如果为空就只序列化不往队列里面放
					ans.add(null);
				}
				if (head.right != null) {
					//右边不为空，进去就序列化
					ans.add(String.valueOf(head.right.value));
					queue.add(head.right);
				} else {
					ans.add(null);
				}
			}
		}
		return ans;
	}

	public static Node buildByLevelQueue(Queue<String> levelList) {
		if (levelList == null || levelList.size() == 0) {
			return null;
		}
		Node head = generateNode(levelList.poll());
		Queue<Node> queue = new LinkedList<Node>();
		if (head != null) {
			queue.add(head);
		}
		Node node = null;
		while (!queue.isEmpty()) {
			node = queue.poll();
			node.left = generateNode(levelList.poll());
			node.right = generateNode(levelList.poll());
			if (node.left != null) {
				queue.add(node.left);
			}
			if (node.right != null) {
				queue.add(node.right);
			}
		}
		return head;
	}

	public static Node generateNode(String val) {
		//要么建立出空node或者带值的node
		if (val == null) {
			return null;
		}
		return new Node(Integer.valueOf(val));
	}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178

    LEETCODE 431(encode-n-ary-tree-to-binary-tree )

    设计一个算法，可以将 N 叉树编码为二叉树，并能将该二叉树解码为原 N 叉树。
    一个 N 叉树是指每个节点都有不超过 N 个孩子节点的有根树。
    类似地，一个二叉树是指每个节点都有不超过 2 个孩子节点的有根树。
    你的编码 / 解码的算法的实现没有限制，你只需要保证一个 N 叉树可以编码为二叉树且该二叉树可以解码回原始 N 叉树即可。
    [将多叉树转换为代表原来结果的二叉树，并且二叉树也能转换为原来的多叉树]
    在这里插入图片描述
    a节点的所有孩子就放在它的左树右边界上，右树直接用#标识，b的所有孩子放在b的左树右边界上面，c和d同理。

    // 本题测试链接：https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree
// 提交时不要提交这个类
	public static class Node {
		public int val;
		public List<Node> children;

		public Node() {
		}

		public Node(int _val) {
			val = _val;
		}

		public Node(int _val, List<Node> _children) {
			val = _val;
			children = _children;
		}
	};

	// 提交时不要提交这个类
	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	// 只提交这个类即可
	class Codec {
		// Encodes an n-ary tree to a binary tree.
		public TreeNode encode(Node root) {
			if (root == null) {
				return null;
			}
			TreeNode head = new TreeNode(root.val);
			//所有孩子往左树右边界上面挂载
			head.left = en(root.children);
			return head;
		}

		private TreeNode en(List<Node> children) {
			TreeNode head = null;
			TreeNode cur = null;
			for (Node child : children) {
				//遍历孩子的时候把二叉树节点给建立出来
				TreeNode tNode = new TreeNode(child.val);
				//如果是第一个则标记第一个，如果不是则挂在前一个的右孩子上面
				if (head == null) {
					//将此时的节点初次设置为head
					head = tNode;
				} else {
					//往cur的右边挂
					cur.right = tNode;
				}
				cur = tNode;
				//当前child的左树右边界是否有子孩子，如果有的话则挂载
				cur.left = en(child.children);
			}
			return head;
		}

		// Decodes your binary tree to an n-ary tree.
		public Node decode(TreeNode root) {
			if (root == null) {
				return null;
			}
			return new Node(root.val, de(root.left));
		}
		//反序列化也是一样的道理
		public List<Node> de(TreeNode root) {
			List<Node> children = new ArrayList<>();
			while (root != null) {
				Node cur = new Node(root.val, de(root.left));
				children.add(cur);
				root = root.right;
			}
			return children;
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81

    求二叉树最宽的层有多少个节点

    思路：
    1、首先要知道这一层是否结束了，以及是在哪结束的，那么就能求得宽度了
    在这里插入图片描述
    curend表示当前层最后一个节点
    nextend表示下一层最后的节点
    max表示最大宽度。
    首先：
    在这里插入图片描述
    将curend设置为1，表示当前根节点进去的那一层结束是在1节点结束的，然后再设置一个变量统计
    当前层有多少个节点
    在这里插入图片描述
    当1弹出了cur节++等于1，然后队列再先进2再进3，将nextend更新为3，将当前的max设置为1，当前层
    节点归0：
    在这里插入图片描述
    最后再更新nextend和curend：
    在这里插入图片描述
    然后2出来，将当前层节点数加1，然后将2的子节点放入进队列里面，此时nextend更新成5，然后判断2
    是不是当前层的最后一个节点呢，2此时不是当前层的最后一个节点，然后弹出3，当前层节点加1，将6
    加入队列里面，将nextend更新为6，然后由于当前节点是当前层的最后一个节点，那么将进行下一层的遍历，
    更新max为2。
    在这里插入图片描述
    此时更新为如下状态：
    在这里插入图片描述
    然后将4弹出，当前层节点数加1，4没有子节点，那么5出来，当前层的节点数加1，然后5有子节点，那么nextend更新为7，然后将7放入队列中，然后5不是当前节点的最后一个，队列继续弹出6，
    发现6有子节点8，将8放入队列中且标记nextend为8，然后将当前层的节点数加1，然后由于6是当前层的
    最后一个节点，那么更新curend以及nextend，并更新max的值
    如下通过两种方式实现：

    	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static int maxWidthUseMap(Node head) {
		if (head == null) {
			return 0;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		// key 在 哪一层，value
		HashMap<Node, Integer> levelMap = new HashMap<>();
		levelMap.put(head, 1);
		int curLevel = 1; // 当前你正在统计哪一层的宽度
		int curLevelNodes = 0; // 当前层curLevel层，宽度目前是多少
		int max = 0;
		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			int curNodeLevel = levelMap.get(cur);
			if (cur.left != null) {
				levelMap.put(cur.left, curNodeLevel + 1);
				queue.add(cur.left);
			}
			if (cur.right != null) {
				levelMap.put(cur.right, curNodeLevel + 1);
				queue.add(cur.right);
			}
			if (curNodeLevel == curLevel) {
				curLevelNodes++;
			} else {
				max = Math.max(max, curLevelNodes);
				curLevel++;
				curLevelNodes = 1;
			}
		}
		max = Math.max(max, curLevelNodes);
		return max;
	}

	public static int maxWidthNoMap(Node head) {
		if (head == null) {
			return 0;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		Node curEnd = head; // 当前层，最右节点是谁
		Node nextEnd = null; // 下一层，最右节点是谁
		int max = 0;
		int curLevelNodes = 0; // 当前层的节点数
		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			//本层在更新同时为下层做准本
			if (cur.left != null) {
				queue.add(cur.left);
				nextEnd = cur.left;
			}
			if (cur.right != null) {
				queue.add(cur.right);
				nextEnd = cur.right;
			}
			curLevelNodes++;//当前层节点数加1
			if (cur == curEnd) {
				//如果当前节点等于当前层的最后一个节点
				max = Math.max(max, curLevelNodes);
				//将当前层节点数清零
				curLevelNodes = 0;
				//然后将下一层的结束节点赋值给这一层
				curEnd = nextEnd;
			}
		}
		return max;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78

    给定二叉树某个节点，返回该二叉树的后继节点

    Class Node {
V value; 
Node left;
Node right;
Node parent; } 
给你二叉树中的某个节点，返回该节点的后继节点

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    方案1：根据给定的头节点，生成一个中序遍历的顺序，然后根据顺序，找到这个x的后续节点（复杂度O(N)）
    方案2：根据parent指针来做：
    分如下情况来讨论：
    （1）x有右树（后续节点是中序遍历中x的下一个，也是右树的最左孩子）
    （2）x没有右树（x的后继节点，为x一直往上找，找到某个节点的左子树指向x的父亲节点）
    在这里插入图片描述

    	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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
  • 相关阅读:
    web前端期末大作业【 大学生抗疫感动专题网页设计】HTML+CSS
    Android 数据存储
    时创能源将于12月7日上会：拟募资11亿元，业绩增长迅猛
    【python】爬虫系列之lxml库介绍和xpath提取网页数据
    ELK + filebeat日志解析、日志入库优化 、logstash过滤器配置属性
    【图文教程】若依前后端分离版本-菜单怎么设置
    利用Python和Selenium编程，实现定时自动检索特定网页，发现特定网页内容发生变化后，向管理员发送提醒邮件（一)
    辅助笔记-Jupyter Notebook的安装和使用
    在windows中使用mysql workbench连接vmware windows虚拟机中的mysql
    【小程序】导航栏和内容页面联动效果实现
  • 原文地址：https://blog.csdn.net/lsdstone/article/details/126201481