二叉树遍历
前序遍历：中、左、右
中序遍历：左、中、右
后序遍历：左、右、中
返回结果
先序：1 2 4 6 7 8 3 5
中序：4 7 6 8 2 1 3 5
后序：7 8 6 4 2 5 3 1
递归实现
// 前序遍历
public static void recursionPreorderTraversal(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
recursionPreorderTraversal(root.left);
recursionPreorderTraversal(root.right);
}
}
// 中序遍历
public static void recursionMiddleorderTraversal(TreeNode root) {
if (root != null) {
recursionMiddleorderTraversal(root.left);
System.out.print(root.val + " ");
recursionMiddleorderTraversal(root.right);
}
}
// 后序遍历
public static void recursionPostorderTraversal(TreeNode root) {
if (root != null) {
recursionPostorderTraversal(root.left);
recursionPostorderTraversal(root.right);
System.out.print(root.val + " ");
}
}
非递归实现
// 非递归先序遍历
public static void preorderTraversal(TreeNode root) {
// 用来暂存节点的栈
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
// 新建一个游标节点为根节点
TreeNode node = root;
// 当遍历到最后一个节点的时候，无论它的左右子树都为空，并且栈也为空
// 所以，只要不同时满足这两点，都需要进入循环
while (node != null || !treeNodeStack.isEmpty()) {
// 若当前考查节点非空，则输出该节点的值
// 由考查顺序得知，需要一直往左走
while (node != null) {
System.out.print(node.val + " ");
// 为了之后能找到该节点的右子树，暂存该节点
treeNodeStack.push(node);
node = node.left;
}
// 一直到左子树为空，则开始考虑右子树
// 如果栈已空，就不需要再考虑
// 弹出栈顶元素，将游标等于该节点的右子树
if (!treeNodeStack.isEmpty()) {
node = treeNodeStack.pop();
node = node.right;
}
}
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
if(node == null)
continue;
ret.add(node.val);
stack.push(node.right);
stack.push(node.left);
}
return ret;
}
// 非递归中序遍历
// 和非递归先序遍历类似，唯一区别是考查到当前节点时，并不直接输出该节点。
// 当考查节点为空时，从栈中弹出的时候再进行输出(永远先考虑左子树，直到左子树为空才访问根节点)。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while(node!=null||!stack.isEmpty()){
while(node!=null){
stack.push(node);
node = node.left;
}
node =stack.pop();
ret.add(node.val);
node = node.right;
}
return ret;
}
// 非递归后序遍历
public static void postorderTraversal(TreeNode root) {
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
TreeNode node = root;
TreeNode lastVisit = root;
while (node != null || !treeNodeStack.isEmpty()) {
while (node != null) {
treeNodeStack.push(node);
node = node.left;
}
//查看当前栈顶元素
node = treeNodeStack.peek();
//如果其右子树也为空，或者右子树已经访问
//则可以直接输出当前节点的值
if (node.right == null || node.right == lastVisit) {
System.out.print(node.val + " ");
treeNodeStack.pop();
lastVisit = node;
node = null;
} else {
//否则，继续遍历右子树
node = node.right;
}
}
}
// 前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
if(node == null)
continue;
ret.add(node.val);
stack.push(node.left);
stack.push(node.right);
}
Collections.reverse(ret);
return ret;
}
}
6. 重建二叉树
描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路
前序遍历找到第一个为根节点，中序遍历可以找到左右子树。递归构建
public class Solution {
private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
if (startPre > endPre || startIn > endIn)
return null;
TreeNode root = new TreeNode(pre[startPre]);
for (int i = startIn; i <= endIn; i++) {
if (in[i] == pre[startPre]) {
root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
root.right = reConstructBinaryTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
}
}
return root;
}
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
if (pre == null || in == null)
return null;
return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
}
}
18. 树的子结构
描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路
- 递归思想，如果根节点相同则递归调用IsSubtree()，如果根节点不相同，则判断
root1的左子树和roo2是否相同，再判断右子树和root2是否相同; - 注意节点为空的条件，
HasSubTree中，只要有树为空就返回false;IsSubtree中，要先判断root2，如果root2为空，则说明第二棵树遍历完了，即匹配成功。
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null){
return false;
}
return IsSubtree(root1, root2) ||
HasSubtree(root1.left, root2) ||
HasSubtree(root1.right, root2);
}
public boolean IsSubtree(TreeNode root1, TreeNode root2){
//要先判断roo2, 不然{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}这个测试用例通不过。
if(root2 == null)
return true;
if(root1 == null)
return false;
if(root1.val == root2.val){
return IsSubtree(root1.left, root2.left) &&
IsSubtree(root1.right, root2.right);
}else
return false;
}
}
19. 二叉树的镜像
思路：递归交换叶子节点
public void Mirror(TreeNode root) {
//当前节点为空，直接返回
if(root == null)
return;
//当前节点没有叶子节点，直接返回
if(root.left == null && root.right == null)
return;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
//递归交换叶子节点
if(root.left != null)
Mirror(root.left);
if(root.right != null)
Mirror(root.right);
}
23. 从上往下打印二叉树
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(root == null)
return list;
Deque<TreeNode> deque = new LinkedList<TreeNode>();
deque.add(root);
while(!deque.isEmpty()){
TreeNode node = deque.pop();
list.add(node.val);
if(node.left!=null)
deque.add(node.left);
if(node.right!=null)
deque.add(node.right);
}
return list;
}
24. 二叉树后续遍历
描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路
二叉搜索树: 左子树<根<=右子树
后序遍历，序列数组的最后一个元素是根节点, 根据这个元素，将前面的数组分为左、右两个部分，左侧部分都比该元素小，右侧部分都比该元素大，如果右侧部分有比该根节点小的元素，那么就不是后序遍历，如此递归进行。
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length == 0) return false;
return IsTreeBST(sequence, 0, sequence.length-1);
}
public boolean IsTreeBST(int [] sequence,int start,int end ){
if(end <= start) return true;
int i = start;
while( i < end && sequence[i] < sequence[root]) {
i++;
}
for (int j = i; j < end; j++) {
if(sequence[j] < sequence[end]) return false;
}
return IsTreeBST(sequence, start, i-1) && IsTreeBST(sequence, i, end-1);
}
25. 二叉树中和为某一值的路径
描述
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
思路
- 用前序遍历的方式访问到某一结点时，把该结点添加到路径上，并用目标值减去该节点的值。
- 如果该结点为叶结点并且目标值减去该节点的值刚好为0，则当前的路径符合要求，我们把加入res数组中。
- 如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到它的父结点。因此我们在函数退出之前要在路径上删除当前结点，以确保返回父结点时路径刚好是从根结点到父结点的路径。
public class Solution {
ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> a1 = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
if (root == null)
return arr;
int sum = 0;
get(root, target, sum);
return arr;
}
public void get(TreeNode root, int target, int sum) {
if (root == null) return;
// 前序遍历开始
sum += root.val;
// 根据是否有子节点判断是否到底
if (root.left == null && root.right == null) {
// 如果值相等，则将该路径放入arr
if (sum == target) {
a1.add(root.val);
arr.add(new ArrayList<Integer>(a1));
// 移出该节点
a1.remove(a1.size() - 1);
}
return;
}
// 该路径放入arr
a1.add(root.val);
get(root.left, target, sum);
get(root.right, target, sum);
// 移出该节点
a1.remove(a1.size() - 1);
}
}
26. 二叉树与双向链表
描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路
- 二叉搜索树中，左子结点的值总是小于父结点的值，右子节点的值总是大于父结点的值。所以转换链表时，原先指向左子节点的指针调整为链表指向前一个结点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。
把二叉树看成三部分
- 因为中序遍历是按照从小到大的顺序遍历二叉搜索树，所以我们用中序遍历树中的每一个节点得到的正好是要求的排好序的。遍历过程如下：
- 每次遍历节点的左孩子、右孩子，把左孩子指向转换链表的尾节点，并把末尾指针的右孩子指向自己
- 右孩子指向节点的右孩子。如果没有右孩子就返回。这一过程可以用递归实现。
/**
* 非递归实现：
* 1.核心是中序遍历的非递归算法。
* 2.修改当前遍历节点与前一遍历节点的指针指向。
*/
public TreeNode ConvertBSTToBiList(TreeNode root) {
if (root == null)
return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
TreeNode pre = null;// 用于保存中序遍历序列的上一节点
boolean isFirst = true;
while (p != null || !stack.isEmpty()) {
while (p != null) {
stack.push(p);
p = p.left;
}
p = stack.pop();
if (isFirst) {
root = p;// 将中序遍历序列中的第一个节点记为root
pre = root;
isFirst = false;
} else {
pre.right = p;
p.left = pre;
pre = p;
}
p = p.right;
}
return root;
}
public class Solution {
TreeNode head = null;
TreeNode end = null;
public TreeNode Convert(TreeNode pRootOfTree) {
ConvertSub(pRootOfTree);
return head;
}
public void ConvertSub(TreeNode pRootOfTree) {
if(pRootOfTree == null)
return ;
Convert(pRootOfTree.left);
if(end == null){
head = pRootOfTree;
end = pRootOfTree;
}else{
end.right = pRootOfTree;
pRootOfTree.left = end;
end = pRootOfTree;
}
Convert(pRootOfTree.right);
}
}
39. 二叉树深度
思路
- 如果根节点左（右）子树为空，则二叉树深度为左（右）子树深度+1
- 如果根节点左右子树不为空，二叉树深度为左子树和右子树中最大深度+1
public int TreeDepth(TreeNode root) {
if(root==null)
return 0;
int x=0,y=0;
if(root.left!=null)
x = TreeDepth(root.left);
if(root.right!=null)
y = TreeDepth(root.right);
return Math.max(x,y)+1;
}
平衡二叉树判断
思路：左右子树深度是否相差1
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
return getDepth(root) != -1;
}
private int getDepth(TreeNode root) {
if (root == null) return 0;
int left = getDepth(root.left);
if (left == -1) return -1;
int right = getDepth(root.right);
if (right == -1) return -1;
return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}
}
58. 二叉树的下一个结点
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解题思路
中序遍历：左 -> 根 -> 右
分三种情况：
- 如果当前节点为空，直接返回空；
- 如果当前节点有右子树，则返回右子树的最左子树；
- 如果当前节点没有右子树，再分两种情况：
- 看看当前节点是不是它的父节点的左子树，如果是，则返回它的父节点；
- 如果当前节点不是它的父节点的左子树，则把父节点赋给当前节点，再判断当前节点是不是它的父节点的左子树，直到当前节点是不是它的父节点的左子树，返回它的父节点。
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null; // 父节点
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode == null){
return null;
}
if(pNode.right != null){
TreeLinkNode node = pNode.right;
while(node.left != null){
node = node.left;
}
return node;
}
while(pNode.next != null){
TreeLinkNode root = pNode.next;
if(pNode == root.left)
return root;
pNode = root;
}
return null;
}
}
59.对称二叉树
题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路
法一：递归。根节点的左右子树相同，左子树的左子树和右子树的右子树相同，左子树的右子树和右子树的左子树相同即可。
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
if(pRoot == null)
return true;
return isSymmetrical(pRoot.left, pRoot.right);
}
boolean isSymmetrical(TreeNode left, TreeNode right){
if(left == null && right == null)
return true;
if(left == null || right == null)
return false;
if(left.val == right.val){
return isSymmetrical(left.left, right.right) &&
isSymmetrical(left.right, right.left);
}
return false;
}
}
法二：非递归，使用栈存放树的节点
- 将左右子树放入栈中
- 弹出左右子树判断val是否相等，不等则返回false
- 相等则按顺序将左子树的左子树、右子树的右子树、左子树的左子树、右子树的左子树放入栈中，循环直到栈为空
import java.util.Stack;
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
if(pRoot == null)
return true;
Stack<TreeNode> s = new Stack<>();
s.push(pRoot.left);
s.push(pRoot.right);
while(!s.isEmpty()){
TreeNode right = s.pop();
TreeNode left = s.pop();
if(right == null && left == null)
continue;
if(right == null || left == null)
return false;
if(right.val != left.val)
return false;
s.push(left.left);
s.push(right.right);
s.push(left.right);
s.push(right.left);
}
return true;
}
}
二叉树打印成多行
题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路
二叉树的层序遍历，用队列来实现。我们需要两个变量，一个start记录当前层已经打印的节点个数，一个end记录前当层所有的节点个数，当 start == end 时，表时当前层遍历完了，就可以开始下一层遍历。
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if (pRoot == null)
return res;
ArrayList<Integer> temp = new ArrayList<Integer>();
Queue<TreeNode> layer = new LinkedList<TreeNode>();
layer.offer(pRoot);
int start = 0, end = 1;
while (!layer.isEmpty()) {
TreeNode node = layer.poll();
temp.add(node.val);
start++;
if (node.left != null)
layer.add(node.left);
if (node.right != null)
layer.add(node.right);
if (start == end) {
start = 0;
res.add(temp);
temp = new ArrayList<Integer>();
end = layer.size();
}
}
return res;
}
61. 二叉树之字形打印（龙摆尾）
思路
就是二叉树的层序遍历，用队列来实现。
两个栈，一个存奇数层点，一个存偶数层点
奇数层打印完毕后，将左右节点放入偶数栈
偶数层打印完毕后，将右左节点放入偶数栈
public class Solution {
public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
int layer = 1;
//s1存奇数层节点
Stack<TreeNode> s1 = new Stack<TreeNode>();
s1.push(pRoot);
//s2存偶数层节点
Stack<TreeNode> s2 = new Stack<TreeNode>();
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
while (!s1.empty() || !s2.empty()) {
if (layer % 2 != 0) {
ArrayList<Integer> temp = new ArrayList<Integer>();
while (!s1.empty()) {
TreeNode node = s1.pop();
if (node != null) {
temp.add(node.val);
System.out.print(node.val + " ");
s2.push(node.left);
s2.push(node.right);
}
}
if (!temp.isEmpty()) {
list.add(temp);
layer++;
System.out.println();
}
} else {
ArrayList<Integer> temp = new ArrayList<Integer>();
while (!s2.empty()) {
TreeNode node = s2.pop();
if (node != null) {
temp.add(node.val);
System.out.print(node.val + " ");
s1.push(node.right);
s1.push(node.left);
}
}
if (!temp.isEmpty()) {
list.add(temp);
layer++;
System.out.println();
}
}
}
return list;
}
}
62. 序列化二叉树
思路
- 对于序列化：使用前序遍历，递归的将二叉树的值转化为字符，并且在每次二叉树的结点不为空时，在转化val所得的字符之后添加一个’,’作为分割; 对于空节点则以 ‘#,’ 代替。
- 对于反序列化：将字符串按照“，”进行分割，插入到队列中，然后依次从队列中取出字符建立节点，递归创建一个二叉树。
/*序列化二叉树
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
String Serialize(TreeNode root) {
if (root == null) {
return "#,";
}
StringBuffer res = new StringBuffer(root.val + ",");
res.append(Serialize(root.left));
res.append(Serialize(root.right));
return res.toString();
}
TreeNode Deserialize(String str) {
String[] res = str.split(",");
Queue<String> queue = new LinkedList<String>();
for (int i = 0; i < res.length; i++) {
queue.offer(res[i]);
}
return pre(queue);
}
TreeNode pre(Queue<String> queue) {
String val = queue.poll();
if (val.equals("#"))
return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = pre(queue);
node.right = pre(queue);
return node;
}
}
63. 二叉搜索树的第K个结点
题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。
思路
二叉搜索树按照中序遍历的顺序打印出来就是排好序的。
中序遍历后读取第K个结点
TreeNode KthNode(TreeNode root, int k) {
if (root == null || k == 0)
return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
int count = 0;
TreeNode node = root;
do {
if (node != null) {
stack.push(node);
node = node.left;
} else {
node = stack.pop();
count++;
if (count == k)
return node;
node = node.right;
}
} while (node != null || !stack.isEmpty());
return null;
}
网友评论