左神算法基础巩固--3

---

二叉树

二叉树的遍历

二叉树的遍历依靠的是递归序，即每一个节点一共可以回到自己三次，也因此根据这个可以得到二叉树的先序遍历，中序遍历，后序遍历

先序遍历

先序遍历（Preorder Traversal）是二叉树遍历的一种方式，其遍历顺序为：
1.访问根节点。
2.先序遍历左子树。
3.先序遍历右子树。
在先序遍历中，根节点是第一个被访问的节点。这种遍历方式常用于创建树的副本或复制树的结构，因为它首先访问根节点，然后再依次访问子节点。
其按递归序来理解便是当第一次来到当前节点时便打印

递归实现先序遍历代码：

import java.util.ArrayList;
import java.util.List;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}public class PreorderTraversal {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preorderHelper(root, result);return result;}private void preorderHelper(TreeNode node, List<Integer> result) {if (node == null) {return;}// 1第一次来到这个函数result.add(node.val);preorderHelper(node.left, result);// 2 第2次来到preorderHelper(node.right, result);//3 第3次来到}
}

非递归实现先序遍历，非递归实现先序遍历的话可以使用栈来实现，我们需要先吧头节点加入栈中再将右子节点压入栈中和左子节点压入栈中，java代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}public class PreorderTraversal {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val); // 访问当前节点// 先压入右子节点，再压入左子节点，以保证左子节点先被访问if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}return result;}
}

中序遍历

中序遍历（Inorder Traversal）是二叉树遍历的一种方式，其遍历顺序为：
中序遍历左子树.
访问根节点.
中序遍历右子树.
在中序遍历中，对于二叉搜索树（BST），遍历的结果会按照节点值的升序排列.这种遍历方式常用于获取二叉搜索树的有序序列.
其按递归序来理解便是当第二次来到当前节点时便打印

递归实现中序遍历代码：

import java.util.ArrayList;
import java.util.List;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}public class InorderTraversal {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorderHelper(root, result);return result;}private void inorderHelper(TreeNode node, List<Integer> result) {if (node == null) {return;}inorderHelper(node.left, result);result.add(node.val);inorderHelper(node.right, result);}
}

非递归实现中序遍历，我们一直向左遍历将遍历到的节点压入栈中直到左子树为空，再弹出栈顶，并开始右子树的遍历，java代码：

后序遍历

后序遍历（Postorder Traversal）是二叉树遍历的一种方式，其遍历顺序为：
后序遍历左子树.
后序遍历右子树.
访问根节点.
在后序遍历中，根节点是最后一个被访问的节点.这种遍历方式常用于删除树的节点或计算树的某些属性时，因为先处理子节点可以确保在处理根节点时，子节点已经被处理完毕
其按递归序来理解便是当第三次来到当前节点时便打印

递归实现后序遍历代码：

import java.util.ArrayList;
import java.util.List;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}public class PostorderTraversal {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();postorderHelper(root, result);return result;}private void postorderHelper(TreeNode node, List<Integer> result) {if (node == null) {return;}postorderHelper(node.left, result);postorderHelper(node.right, result);result.add(node.val);}
}

非递归实现后序遍历，我们先创建处两个栈，在第一个栈中我们先压入头节点，之后循环将第一个栈中的当前节点压入到第二个栈中，同时先压入当前节点的左节点，再压入当前节点的右节点，之后再遍历输出第二个栈中的内容便是后序遍历，java代码：

解答

二叉树的宽度优先遍历

在二叉树的宽度优先遍历中我们采用队列的方式实现，我们先将头节点加入队列，并将队列中的节点弹出，同时将弹出节点的左右节点压入队列，后不断循环直到队列为空。

将上述代码进行修改便能得到上述问题的解，我们只需要加入一个当前的层数的变量和一个当前的层数有多少节点的变量便能够解决

我们先创建一个HashMap用来存储每个节点在哪一层，同时在进行宽度优先遍历的时候，每遍历到一个节点就判断他与当前的层数是否相等相等便更新当前的层数的节点数，如果不相等便将树的最大节点数与当前层数的节点数相比较如果大于树的层的最大节点数便更新树的层的最大节点数。

面对这种题我们可以使用中序遍历解决，我们直接中序遍历这棵树，并将其所有节点都加入到一个数组中，遍历这个数组判断其是否为升序数组，如果是返回true，如果不是返回false
我们也可以使用另一种方式解答这道题： 我们首先需要明确的是判断一棵树是否为二叉搜索树是由其左子树和右子树以及当前节点决定的，当一棵树的左子树不为二叉搜索树或其右子树不为二叉搜索树或当前节点小于或等于其前一个节点，均能认为这棵树不为二叉搜索树。因此我们可以用递归的方法解决这个问题，我们先用递归的方法判断其左子树是否为二叉搜索树，如果不是便直接返回该树不是二叉搜索树，如果是再进行判断当前当前节点死否小于或等于其前一个节点，如果是便返回该数不是二叉搜索树，如果不是便更新前一个节点的值，再对右子树进行判断。

---

一颗完全二叉树具有以下特征：1.不存在任何一个节点具有右子树但不存在左子树.2.不存在任何一个节点在满足1的情况下左右子树不全且其后续节点不为叶子节点
根据以上特征我们便可以解决上述问题代码如下：
leaf就是是否遇到了左右子树不双全的情况。

判断一棵树是否为满二叉树可以运用二叉树树形dp问题的套路解决，即向他的左右子树要信息，以此题为例，判断一个二叉树是否为满二叉树，我们需要知道这棵树的高度和这棵树的节点个数，即我们需要向每个节点的父节点返回以自己为头节点的子树有多少个节点，以及以自己为头节点的子树的高度是什么，这些信息可以封装起来方便返回。

故这道题的解题思路为，我们先得到当前节点的左子树的信息和右子树的信息，然后，我们根据这些信息得到我们需要返回的以当前节点为头节点的子树的高度，之后我们再根据左右子树的信息得到以当前节点为头节点的子树的节点树，最后拼接成自己需要返回的信息返回。

这道题的解题代码为：

---

判断一棵树是否是平衡二叉树可以运用二叉树树形dp问题的套路解决，即向他的左右子树要信息，以此题为例，判断一棵二叉树是否是平衡二叉树，我们需要知道其左子树的是否为平衡二叉树，其右子树是否为平衡二叉树，以及其左子树的高度和其右子树的高度。即我们需要向每个节点的父节点返回以自己为头节点的子树是否平衡，以自己为头节点的子树的深度，这些信息可以封装起来方便返回。

故这道题的解题思路为，我们先得到当前节点的左子树的信息和右子树的信息，然后，我们根据这些信息得到我们需要返回的以当前节点为头节点的子树的高度，之后我们再根据左右子树的信息得到当前节点是否平衡（根据左子树是否平衡，右子树是否平衡，左右子树的高度差是否小于2），最后拼接成自己需要返回的信息返回。

这道题的解题代码为：

---

这道题与上面的几道题虽然都需要运用递归的方法进行求解但却有些不同，在求解该题时，我们需要先需要找到每个节点的父节点，并存储起来，之后再找到node1的父节点和各个祖先节点并存储。之后再让node2在node1的父节点和各个祖先节点找到相同的最低公共祖先节点

这道题的解题代码如下：


我们也可以采用更为简单的方法，即从头查找，寻找以当前节点为头的子树是否存在node1或node2如果是则说明当前节点是node1或node2的祖宗节点

---

在解这道题中，我们可以直接中序遍历这棵树并将其存储到一个数组中，之后遍历这个数组得到node节点的后继节点
当然我们也可以使用另一种更加省时省力的方法解决
解题思路：当node节点有右子树的时候，其后继节点即为其右子树的最左节点，当node节点没有右子树的时候node节点的后继节点为以x为左树的父节点

---

我们可以用_表示节点的值到此为止，用#表示null，则先序序列化便显而易见了，我们只需要在先序遍历的基础了添加上述约定的字符

反序列化则是依据先序遍历和上述约定画出一棵树

---

解该问题时我们需要总结出一个规律那就是每次折叠都是在原来的基础上往上添加down往下添加up 有这个规律后，我们直接遍历生成便能解决问题