数据结构之二叉树由浅入深最终章!

题外话

我说清明节想放松一下没更新大家信吗?

博客毕竟是文字不是视频,大家如果有不明白的地方,可以使用数形结合的方式,画图一边通过图片,一边通过对照代码进行推导一下,有什么问题都可以私信我或者写在评论区

正题

第一题

寻找二叉树中p,q最近公共祖先

第一题思路

先分析有几种情况

1.p,q在二叉树root的两侧

分别寻找p,q如果都找到了则说明在两侧,root就是最近公共祖先直接返回root即可

2.p,q有一个在根节点root

直接返回根节点

3.p,q在同一侧

先找到p或q直接返回,再继续遍历,如果只找到一个p或q,说明找到的是最近公共祖先

第一题代码及详解

public TreeNode  lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
    //判断root是不是空,空直接返回
    if (root==null)
    {
        return root;
    }
    //如果root找到了p或者q直接返回root,继续遍历,找剩下的结点
    if (root==p||root==q)
    {
        return root;
    }
    //从左子树和右子树一起遍历
    TreeNode left=lowestCommonAncestor(root.left,p,q);
    TreeNode right=lowestCommonAncestor(root.right,p,q);
    //如果p或q有一个没有找到,left或right就会返回空,两个都找到了都不为空,证明p,q在二叉树两边
    if (left!=null&&right!=null)
    {
        //两个都不为空则说明在两边,根节点就是最近公共祖先,直接返回根节点即可
        return root;
    }
    //如果left不为空,right为空则说明left就是最近公共祖先
    else if (left!=null&&right==null){
        return left;

    }
    //否则left为空,right不为空,说明right为最近公共祖先
    else {
       return right;
    }

}

第二题

从前序遍历与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

第二题思路

只需要从先序遍历数组中一个一个找到中序遍历对应的元素从根,左,右创建二叉树即可

第二题代码详解

class Solution {

//创建一个全局变量index,让先序遍历数组每个元素都找到中序遍历数组对应的元素

int index=0;

创建方法buildTree,传入先序遍历数组和中序遍历数组

public TreeNode buildTree(int[] preorder, int[] inorder)

{

return buildTreeChilde(preorder,inorder,0,inorder.length-1);

}

//创建方法buildTreeChilde,传入先序遍历数组,中序遍历数组,中序遍历开始下标,和中序遍历最后一个元素下标

private TreeNode buildTreeChilde(int[] preorder,int[] inorder,int inbegin,int inend)

{

//如果inbegin大于inend说明遍历完毕

if (inbegin>inend)

{

return null;

}

//建立对象root用于创建连接二叉树

TreeNode root=new TreeNode(preorder[index]);

//创建rootIndex接收找到对应先序遍历数组元素对应中序遍历数组元素下标

int rootIndex=findIndexRoot(inorder,inbegin,inend,preorder[index]);

//如果下标为-1则说明没找到(但基本上不可能找不到)

if (rootIndex==-1)

{

return null;

}

//找到之后,继续往后创建下一个元素,index++

index++;

//将找到元素前一个作为左子树(因为中序遍历是左,根,右,根结点前一个元素就是左子树)

root.left=buildTreeChilde(preorder,inorder,inbegin,rootIndex-1);

//将找到元素后一个作为右子树

root.right=buildTreeChilde(preorder,inorder,rootIndex+1,inend);

return root;

}

//寻找先序遍历数组元素对应的中序遍历数组下标

private int findIndexRoot(int[] inorder,int inbegin,int inend,int key )

{

for (int i = 0; i <= inend; i++) {

if (inorder[i]==key)

{

return i;

}

//没找到返回-1

return -1;

}

第三题

根据中序和后序遍历返回二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

第三题思路

根据后序遍历,左右根,从最后往前在中序遍历中找到对应元素,先建立根节点再建立右子树最后建立左子树,因为遍历的时候是左右根,创建的时候顺序为根有左的顺序

第三题代码详解

class Solution {

//创建一个全局变量postIndex,让后序遍历数组每个元素都找到中序遍历数组对应的元素

int postIndex;

//创建方法buildTree,传入后序遍历数组和中序遍历数组

public TreeNode buildTree( int[] inorder,int[] postorder)

{

//让postIndex为后序遍历最后一个下标

postIndex=postorder.length-1;

return buildTreeChilde(postorder,inorder,0,inorder.length-1);

}

//创建方法buildTreeChilde,传入后序遍历数组,中序遍历数组,中序遍历开始下标,和中序遍历最后一个元素下标

private TreeNode buildTreeChilde(int[] postorder,int[] inorder,int inbegin,int inend)

{

//如果inbegin大于inend说明遍历完毕

if (inbegin>inend)

{

return null;

}

//建立对象root用于创建连接二叉树

TreeNode root=new TreeNode(postorder[postIndex]);

//创建rootIndex接收找到对应后序遍历数组元素对应中序遍历数组元素下标

int rootIndex=findIndexRoot(inorder,inbegin,inend,postorder[postIndex]);

//如果下标为-1则说明没找到(但基本上不可能找不到)

if (rootIndex==-1)

{

return null;

}

//找到之后,继续往前创建下一个元素,postIndex--

postIndex--;

//将找到元素后一个作为右子树

root.right=buildTreeChilde(postorder,inorder,rootIndex+1,inend);

//将找到元素前一个作为左子树

root.left=buildTreeChilde(postorder,inorder,inbegin,rootIndex-1);

return root;

}

//寻找后序遍历数组元素对应的中序遍历数组下标

private int findIndexRoot(int[] inorder,int inbegin,int inend,int key )

{

for (int i = 0; i <= inend; i++) {

if (inorder[i]==key)

{

return i;

}

//没找到返回-1

return -1;

}

第四题

根据二叉树创建字符串

给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

第四题思路

这道题主要是看这两个例子,根据这两个例子咱们分析一下

1.用前序遍历思路

2.根结点直接放入StringBuilder中

3.如果左子树或者右子树不为空,直接在StringBuilder中添加"("

4.左子树不为空,就继续遍历左子树,在StringBuilder中添加")"

5.左子树为空,右子树不为空在StringBuilder中添加"()",左右子树都为空直接返回

6.右子树不为空,就继续遍历右子树,在StringBuilder中添加")"

7.右子树为空,直接返回

第四题代码

//创建全局变量 StringBuilder s

StringBuilder s=new StringBuilder();

public String tree2str(TreeNode root) {

//调用 tree2strChild()方法

tree2strChild(root);

//返回s.toString方法

return s.toString();

}

public void tree2strChild(TreeNode root) {

//当结点为空,直接返回

if(root==null)

{

return;

}

//结点不为空直接将val添加s中

s.append(root.val);

//如果结点左子树不为空

if (root.left!=null)

{

//先添加左括号

s.append("(");

//递归遍历左子树

tree2strChild(root.left);

//添加右括号

s.append(")");

}

else {

//如果左子树为空,右子树不为空

if (root.right!=null)

{

//添加一对小括号

s.append("()");

}

//如果左子树为空,右子树也为空

else {

return;

}

//如果右子树不为空

if(root.right!=null)

{

//先添加左括号

s.append("(");

//再递归遍历右子树

tree2strChild(root.right);

//再添加右括号;

s.append(")");

}

else {

return;

}

第五题

二叉树非递归前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

第五题思路

不用递归前序遍历,我们需要借助别的方法,之前层序遍历我们用的队列,因为队列是先进先出原则

而这里我们用队列无法实现前序遍历(大家可以自己推导一下,如果用队列什么时候出队,什么时候打印结点,就会发现有矛盾的地方)

这里我们用的是栈来实现前序遍历,先进后出原则,我们需要思考以下的问题

1.如何才能实现像递归一样,根左子树右子树这样一直遍历

2.什么时候打印

3.什么时候出栈

1.首先,我们可以用while从根左子树右子树循环,但是只依靠一个while无法实现多重循环,我们要使用两个while,才可以实现像递归一样

大家可以思考一下,如果把一个方法放入while中,意味着只要满足while条件,就会一直循环这个方法

那么这就可以实现类似递归的操作了

2.打印的时机有两个,一个是进栈,一个是出栈,栈遵循先进后出

我们以根,左,右的顺序进栈,但是出栈绝对是右子树会比左子树先出栈,所以出栈打印结点无法实现前序遍历

那么进栈的时候我们就可以边进栈边打印结点

3.我们要先进栈,当左子树遍历完成之后,然后才能出栈,出栈的时候要把出栈结点保存,从而找到它的右子树

第五题代码详解

public void preorderTraversal(TreeNode root) {
//创建栈s
    Stack<TreeNode> s=new Stack<>();
//当结点为空直接返回
    if (root==null)
    {
        return;
    }
//创建临时变量cur,把root赋值给cur
    TreeNode cur=root;
//当cur不为空或者栈中元素没有全部出栈(不为空)
    while (cur!=null||!s.empty()) {
//只要cur不为空
         while (cur!=null) {
//将结点放入栈中,并打印该结点
              s.push(cur);
              System.out.println(cur.val+" ");
//让结点等于其左子树,继续循环
              cur=cur.left;
          }
//当cur为空了,也就是左子树为空了,该遍历右子树了,将栈顶元素,也就是根结点出栈,并指向其右子树
        cur=s.pop();
         cur=cur.right;
    }
}

第六题

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

非递归中序遍历

第六题思路

和第五题差不太多

区别就是打印时机和出栈时机

中序遍历是左根右,我们应该把根的左子树都遍历完成,然后再出栈最后一个左子树(先进后出)并保存,然后找其右子树,循环往复即可

第六题代码详解

public void inorderTraversal(TreeNode root) {
//创建栈s
    Stack<TreeNode> s=new Stack<>();
//如果结点为空直接返回
    if (root==null)
    {
        return;
    }
//创建临时变量cur接收root
    TreeNode cur=root;
//当cur不为空或者栈不为空时
    while (cur!=null||!s.empty()) {
//当cur不为空
        while (cur!=null) {
//先入栈
            s.push(cur);
//赋值结点左子树循环往复
            cur=cur.left;
        }
//出栈最后入栈结点(先进后出)并保存出栈结点
        cur=s.pop();
//打印出栈结点值
        System.out.println(cur.val+" ");
//让cur等于其右子树,再次循环
        cur=cur.right;
    }
}