取材于LeetCode的探索卡片（二叉树）
概念
树 是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。
树里的每一个节点有一个根植和一个包含所有子节点的列表。从图的观点来看，树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。
二叉树是一种更为典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。
树的遍历
前序遍历
前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
代码
简单说一下stack的库函数
stack.isempty() 判断栈是否为空，空返回true，非空false
stack.peek() 查看栈顶元素
stack.pop() 移除栈顶元素，并作为函数返回值
stack.push() 入栈
/**
* 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> preorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
getPreOrder(root,list);
return list;
}
private void getPreOrder(TreeNode root,List<Integer> list){
if(root == null){
return ;
}
list.add(root.val);
getPreOrder(root.left,list);
getPreOrder(root.right,list);
}
//非递归：通常利用栈的特性保存节点顺序，入一个出一个且只入根节点和左孩子
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if(root == null){
return result;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode p = root;
// 当前节点非空 或 栈非空
while(p != null || !stack.isEmpty()){
if(p != null){ //节点非空
result.add(p.val);
stack.push(p); // 入栈
p = p.left; // 找左孩子
}else{ //节点为空但栈非空
p = stack.pop().right; //先删除栈顶元素再找该栈顶元素的右孩子
}
}
return result;
}
}
中序遍历
中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
代码
/**
* 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<>();
getinorder(root,list);
return list;
}
private void getinorder(TreeNode root,List<Integer> list){
if(root == null){
return ;
}
getinorder(root.left,list);
list.add(root.val);
getinorder(root.right,list);
}
}
//非递归
//1.先将根节点入栈
//2.将当前节点的所有左孩子入栈，直到左孩子为空
//3.访问栈顶元素，并删除栈顶元素，若存在右孩子，则继续第2步
//4.重复第2、3步，直到栈为空并且所有的节点都被访问
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
//1.先将根节点入栈
//2.将当前节点的所有左孩子入栈，直到左孩子为空
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
//3.访问栈顶元素，并删除栈顶元素，若存在右孩子，则继续第2步
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
后序遍历
后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//递归
class Solution {
List<Integer> result = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return result;
}
postorderTraversal(root.left);
postorderTraversal(root.right);
result.add(root.val);
return result;
}
}
//非递归
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> s=new Stack<>();
//辅助栈，用来存储遍历顺序
Stack<Integer> tmp = new Stack<>();
while(root != null || !s.empty()){
//将节点的所有右节点推入栈s，值推入栈tmp，保证了栈tmp先进根节点再进右孩子节点
while (root != null) {
tmp.add(root.val);
s.push(root);
root = root.right;
}
// 栈s非空，说明该节点从右孩子节点返回父节点
// 删除栈顶元素，并返回栈顶元素的左孩子节点
//保证了最后进栈tmp的是左孩子节点
//重复上一步
if (!s.empty()) {
root = s.pop().left;
}
}
//栈tmp推栈顺序为根节点，右节点，左节点，先进后出特性出栈即为后序遍历
while(!tmp.empty()){
res.add(tmp.pop());
}
return res;
}
层序遍历
层序遍历就是逐层遍历树结构。
代码
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
helper(res, root, 0);
return res;
}
public void helper(List<List<Integer>> res, TreeNode root, int height) {
if (root == null) return;
if (height ==res.size()) { //妙啊，每一层建立一个新list
res.add(new ArrayList<>());
}
res.get(height).add(root.val);
helper(res, root.left, height+1);
helper(res, root.right, height+1);
}
}
运用递归解决问题
“自顶向下” 的解决方案
“自顶向下” 意味着在每个递归层级，我们将首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。 所以 “自顶向下” 的解决方案可以被认为是一种前序遍历。
例如，思考这样一个问题：给定一个二叉树，请寻找它的最大深度。
我们知道根节点的深度是1。 对于每个节点，如果我们知道某节点的深度，那我们将知道它子节点的深度。 因此，在调用递归函数的时候，将节点的深度传递为一个参数，那么所有的节点都知道它们自身的深度。 而对于叶节点，我们可以通过更新深度从而获取最终答案。
代码
private int answer; // don't forget to initialize answer before call maximum_depth
private void maximum_depth(TreeNode root, int depth) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
answer = Math.max(answer, depth);
}
maximum_depth(root.left, depth + 1);
maximum_depth(root.right, depth + 1);
}
“自底向上” 的解决方案
自底向上” 是另一种递归方法。 在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。 这个过程可以看作是后序遍历的一种。
让我们继续讨论前面关于树的最大深度的问题，但是使用不同的思维方式：对于树的单个节点，以节点自身为根的子树的最大深度x是多少？
如果我们知道一个根节点，以其左子节点为根的最大深度为l和以其右子节点为根的最大深度为r，我们是否可以回答前面的问题？ 当然可以，我们可以选择它们之间的最大值，再加上1来获得根节点所在的子树的最大深度。 那就是 x = max（l，r）+ 1。
这意味着对于每一个节点来说，我们都可以在解决它子节点的问题之后得到答案。 因此，我们可以使用“自底向上“的方法。
public int maximum_depth(TreeNode root) {
if (root == null) {
return 0; // return 0 for null node
}
int left_depth = maximum_depth(root.left);
int right_depth = maximum_depth(root.right);
return Math.max(left_depth, right_depth) + 1; // return depth of the subtree rooted at root
}
总结：
当遇到树问题时，请先思考一下两个问题：
1 你能确定一些参数，从该节点自身解决出发寻找答案吗？
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 int maxDepth(TreeNode root) {
return root==null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}
进阶参考题目：（这些题目都可以从LeetCode上收到）
从中序与后序遍历序列构造二叉树
从前序与中序遍历序列构造二叉树
填充每个节点的下一个右侧节点指针
二叉树的最近公共祖先
二叉树的序列化与反序列化
转载：https://blog.csdn.net/qq_28295947/article/details/105849180