1. 前序遍历
题目解析:
题目:
. - 力扣（LeetCode）
解题步骤:
题目给定的返回值是一个链表,也就是我们每一次前序遍历都要把遍历结果保存到顺序表里面进行返回.
前序遍历: 根结点 -> 左子树 -> 右子树
我们的遍历过程如图
就相当于所有的结点 = 根结点 + 所有的左子树根结点 + 所有的右子树根结点
我们就此拆分问题,每次递归我们都把结点放进顺序表,当我们把每一棵子树的根结点和树的根结点都加入到链表中,就完成了.
但是我们的上述过程没有很好的利用我们的返回值.
我们来优化一下,我们把每次的顺序表返回值给利用起来,整个二叉树的顺序表 = 所有左子树的小链表 + 所有右子树的小链表.
具体代码:
1> 定义全局顺序表,遍历一个加入一个
List<Integer> list1 = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {//先判断根结点为不为空if (root == null) {return list1;}//不为空就把根结点加入顺序表list1.add((int) root.val);//遍历根结点的左子树preorderTraversal(root.left);//遍历根结点的右子树preorderTraversal(root.right);return list1;//如何合理利用返回值?}2> 定局部顺序表,利用方法返回值
public List<Integer> preorderTraversal2(TreeNode root) {List<Integer> list = new ArrayList<>();//先判断根结点为不为空if (root == null) {return list;}//不为空就按照根左右的方式来打印;list.add((int) root.val);//遍历根结点的左子树List<Integer> leftTree = preorderTraversal2(root.left);//把左边的树放进去list.addAll(leftTree);//遍历根结点的右子树List<Integer> rightTree = preorderTraversal2(root.right);//把右边的树放进去list.addAll(rightTree);return list;}2. 中序遍历
题目解析:
题目
. - 力扣（LeetCode）
步骤: 我们同上述前序遍历
中序遍历: 左子树 -> 根结点 -> 右子树
我们也用俩种方法:第一种每次遍历到左子树就先把左子树的根结点先加入,加完左子树后再加根结点,最后再加入右子树.第二种方法就是利用返回值,我们把先把左子树的顺序表加入,然后我们再加入根结点的顺序表,最后加入右子树的顺序表
具体代码:
1> 使用全局顺序表,采用中序遍历顺序加入结点
List<Integer> list = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {if (root == null) {return list;}inorderTraversal(root.left);list.add((int)root.val);inorderTraversal(root.right);return list;}2> 使用局部顺序表,先加入左子树的顺序表,再加入根结点,最后加入右子树的顺序表(充分利用返回值)
//使用返回值public List<Integer> inorderTraversal2(TreeNode root) {List<Integer> subList = new ArrayList<>();if (root == null) {return subList;}//先把左子树加进去List<Integer> listLeft = inorderTraversal(root.left);subList.addAll(listLeft);//再把根结点加进去subList.add((int)root.val);//最后把右子树加进去List<Integer> listRight = inorderTraversal(root.right);subList.addAll(listRight);return subList;}3. 后序遍历
题目解析:
题目:
145. 二叉树的后序遍历 - 力扣（LeetCode）
步骤:
后序遍历: 左子树 -> 右子树 -> 根结点
我们就按照这个遍历方式加入结点或者顺序表即可
具体代码:
1> 使用全局顺序表,按照后续遍历的顺序,把左右子树的根结点先放入顺序表,最后再把根结点放入
List<Integer> list2 = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {if(root == null) {return list2;}postorderTraversal(root.left);postorderTraversal(root.right);list2.add((int)root.val);return list2;}2> 使用局部顺序表,先把左右顺序表加进去,最后加入根
public List<Integer> postorderTraversal1(TreeNode root) {List<Integer> subList = new ArrayList<>();if(root == null) {return subList;}List<Integer> leftList = postorderTraversal(root.left);subList.addAll(leftList);List<Integer> rightList = postorderTraversal(root.right);subList.addAll(rightList);subList.add((int)root.val);return subList;}4. 检查俩颗树是否相同
题目:
. - 力扣（LeetCode）
题目解析:
我们判断俩棵树是不是相等,我们就需要判断俩个点:
1. 这俩颗树的结构相同
2. 这俩颗树的每一个结点的值相同
因此我们在前序遍历的基础上,我们分别判断上述条件即可
具体代码:
public boolean isSameTree(TreeNode p, TreeNode q) {//我们同样通过遍历来完成: 结构 + 值//如果一个二叉树为空,另一个不为空,那么直接返回false,if((p == null && q != null) || (p != null && q == null)) {return false;}//如果都为空if(p == null && q == null){return true;}//先判断根结点是不是一样的if(p.val != q.val) {return false;}//此时我们的俩个结点在这一刻是根结点的值一样,且不为空//我们再判断左子树return isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);}5. 另一颗树的子树
题目解析:
题目:
. - 力扣（LeetCode）
我们判断一棵树是不是另一棵树的子树,只需要看俩个地方
1. 俩颗树是否完全一样
2. 一棵树是另一颗子树
俩颗树完全相同题目4已经写了方法,我们直接调用即可
主要是判断2
这个我们有俩个需要注意的点:
1> if(root == null || subRoot == null) 这个是防止空指针异常的条件,我们解释如下
2. 关于里面的遍历操作我们为什么不用isSame要用isSub
具体代码:
public boolean isSameTree(TreeNode p, TreeNode q) {//判断头节点是不是一边是空的if((p == null && q != null) ||(p != null && q == null)) {return false;}//如果全是空的,那么结构一样if(p == null && q == null) {return true;}//如果都不为空,那么我们判断值是否一样if(p.val != q.val) {return false;}//判断左子树和右子树是不是一样的return isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);}//TODO 相同结点的子树//如果俩颗树完全相同,这个是满足的//如果一个树是另一个树的子树,也是满足的(也就是判断是不是左子树或者右子树)//会使用到刚刚的判断俩颗树是否相同的那个代码:isSameTree//时间复杂度:o(n*m)每一个结点判断是不是相同public boolean isSubtree(TreeNode root, TreeNode subRoot) {//防止空指针异常if(root == null || subRoot == null) {return false;}//俩颗树完全一样的情况if(isSameTree(root,subRoot)){return true;}//如果一个是另一个的子树return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);}6. 翻转二叉树
题目解析:
题目:
. - 力扣（LeetCode）
翻转二叉树,意思就是把所有的左子树和右子树进行交换,我们就和下面这么操作即可,首先我们先判断这棵树是不是空,然后我们得到左右子树的地址,然后进行交换即可.
具体代码:
public TreeNode invertTree(TreeNode root) {//先判断是不是空if (root == null) {return root;}//得到左右结点TreeNode rootLeft = invertTree(root.left);TreeNode rootRight = invertTree(root.right);//交换左右结点的地址root.left = rootRight;root.right = rootLeft;return root;}
