自学内容网 自学内容网

二叉树(链式存储)

一、树的基础概念

(1)树是一种非线性的数据结构。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。同理,作为“树”,它只有一个根节点,且同级节点中没有相交关系
(2)树有三种表示方法,其中最常用的是【孩子兄弟表示法】

在这里插入图片描述

-------重要-------------------------
结点的度:一个结点含有子树的个数称为该结点的度
树的度:一棵树中,所有结点度的最大值称为树的度
叶子结点或终端结点:度为0的结点称为叶子结点
双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点
孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点
根结点:一棵树中,没有双亲结点的结点
结点的层次/深度:从根开始定义起,根为第1层,根的子结点为第2层,以此类推
树的高度或深度:树中结点的最大层次

-------了解-------------------------
非终端结点或分支结点:度不为0的结点
兄弟结点:具有相同父结点的结点互称为兄弟结点
堂兄弟结点:双亲在同一层的结点互为堂兄弟
结点的祖先:从根到该结点所经分支上的所有结点
子孙:以某结点为根的子树中任一结点都称为该结点的子孙
森林:由m(m>=0)棵互不相交的树组成的集合称为森林

二、二叉树

2.1 概念 + 性质

  1. 二叉树是指分叉最多为2的树,是树的一种
  2. 一个二叉树要么为空,要么就是根节点、右子树、左子树酌情有
  3. 二叉树有两种特殊的类别,分别是满二叉树和完全二叉树。其中,满二叉树是一种特殊的完全二叉树
    • 满二叉树:一棵二叉树,每层都放满了
    • 完全二叉树:没放满,但是是按照顺序放节点

❤️二叉树的性质
在这里插入图片描述
在这里插入图片描述

2.2 二叉树的存储

  • 顺序存储:优先级队列(堆)
  • 类似于链表的链式存储:通过一个一个的节点引用起来的,常见的表示方式有孩子表示法和孩子双亲表示法
// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
Node parent; // 当前节点的根节点
}

2.2 二叉树的基本操作

手动创建一棵二叉树

public class BinaryTree {
    static class TreeNode{
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(char val){
            this.val = val;
        }
    }

    public TreeNode createTree(){
        TreeNode node1 = new TreeNode('A');
        TreeNode node2 = new TreeNode('B');
        TreeNode node3 = new TreeNode('C');
        TreeNode node4 = new TreeNode('D');
        TreeNode node5 = new TreeNode('D');
        TreeNode node6 = new TreeNode('D');
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node4.right = node5;
        node3.left = node6;

        return node1;
    }
}

遍历:前、中、后、层序

  1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树
public void preOrder1(TreeNode root){
    if (root == null){
        return;
    }
    System.out.print(root.val + " ");
    preOrder1(root.left);
    preOrder1(root.right);

}
//用 List 但是没有用到返回值
List<Integer> ret = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
    if(root == null) return ret;
    //System.out.print(root.val+" ");
    ret.add(root.val);
    preorderTraversal(root.left);
    preorderTraversal(root.right);
    return ret;
}
//用上了返回值
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    if(root == null) return ret;
    ret.add(root.val);
    List<Integer> leftTree = preorderTraversal(root.left);
    ret.addAll(leftTree);
    List<Integer> rightTree = preorderTraversal(root.right);
    ret.addAll(rightTree);
    return ret;
}
  1. 中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树
public void inOrder1(TreeNode root){
    if (root == null){
        return;
    }
    inOrder1(root.left);
    System.out.print(root.val + " ");
    inOrder1(root.right);

}


List<Character> ret = new ArrayList<>();
public List<Character> inOrder2(TreeNode root){
    if (root == null){
        return ret;
    }

    inOrder2(root.left);
    ret.add(root.val);
    inOrder2(root.right);

    return ret;
}
public List<Character> inOrder(TreeNode root){
    List<Character> ret = new ArrayList<>();
    if (root == null){
        return ret;
    }

    List<Character> leftTree = inOrder(root.left);
    ret.addAll(leftTree);
    ret.add(root.val);

    List<Character> rightTree = inOrder(root.right);
    ret.addAll(rightTree);

    return ret;

}
  1. 后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点
public void postOrder1(TreeNode root){
    if (root == null){
        return;
    }
    postOrder1(root.left);

    postOrder1(root.right);
    System.out.print(root.val + " ");
}
List<Character> ret = new ArrayList<>();
public List<Character> postOrder2(TreeNode root){
    if (root == null){
        return ret;
    }

    postOrder2(root.left);
    postOrder2(root.right);
    ret.add(root.val);

    return ret;
}

public List<Character> postOrder(TreeNode root){
    List<Character> ret = new ArrayList<>();
    if (root == null){
        return ret;
    }

    List<Character> leftTree = postOrder(root.left);
    ret.addAll(leftTree);


    List<Character> rightTree = postOrder(root.right);
    ret.addAll(rightTree);
    ret.add(root.val);
    return ret;

}
  1. 层序遍历
    • 此处用非递归的方式更简单,需要创建一个队列来辅助我们,遍历这棵树,root如果不为空就把他放到队列里。如果队列不为空就提出首部元素,然后打印该元素,并把该元素的左右结点放进来
    • 如果想要有 List<List< Integer>> 类型的返回值,我们可以通过记录队列的大小来判断当前是在第几层
    • 层序遍历变种题:求二叉树的左视图
      在这里插入图片描述
//无返回值的层序遍历
public void levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    if(root != null) {
        queue.offer(root);
    }
    
    while (!queue.isEmpty()) {
        TreeNode top = queue.poll();
        System.out.print(top.val+" ");
        if(top.left != null) {
            queue.offer(top.left);
        }
        if(top.right != null) {
            queue.offer(top.right);
        }
    }

}
//有返回值的层序遍历
public List<List<Integer>> levelOrder2(TreeNode root) {
    List<List<Integer>> ret = new ArrayList<>();
    if(root == null) {
        return ret;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();//这一层节点的个数
        List<Integer> list = new ArrayList<>();
        
        while (size != 0) {
            TreeNode top = queue.poll();
            list.add(top.val);
            if(top.left != null) {
                queue.offer(top.left);
            }
            if(top.right != null) {
                queue.offer(top.right);
            }
            size--;
        }
        ret.add(list);
    }
    return ret;
}

获取树中节点的个数

// 遍历,只要 root 不为空就可以++
 public static int usedSize = 0;
 public int size(TreeNode root) {
     if(root == null) {
         return 0;
     }
     usedSize++;
     size(root.left);
     size(root.right);
     return usedSize;
 }

//左树结点 + 右树结点 + 1 = 整棵树的结点
 public int size2(TreeNode root) {
     if(root == null) {
         return 0;
     }
     return  size2(root.left) + size2(root.right) + 1;
 }

获取叶子节点的个数

// 遍历,只要 root 不为空就可以++
 public static int leafSize = 0;
 public int getLeafNodeCount(TreeNode root) {
     if(root == null) {
         return 0;
     }
     if(root.left == null && root.right == null) {
         leafSize++;
     }
     getLeafNodeCount(root.left);
     getLeafNodeCount(root.right);
     return leafSize;
 }

//左树结点 + 右树结点 + 1 = 整棵树的结点
 public int getLeafNodeCount2(TreeNode root) {
     if(root == null) {
         return 0;
     }
     if(root.left == null && root.right == null) {
         return 1;
     }
     return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
 }

获取第K层节点的个数

 public int getKLevelNodeCount(TreeNode root, int k) {
     if(root == null) {
         return 0;
     }
     if(k == 1) {
         return 1;
     }
     return getKLevelNodeCount(root.left,k-1)
             + getKLevelNodeCount(root.right,k-1);
 }

获取二叉树的高度

  1. 核心:【左数的高度】和【右树的高度】之间,取最大值
    • 【左数的高度】和【右树的高度】怎么求?
      在这里插入图片描述
  2. 方式二有漏洞,会超出时间限制
    • 超出时间限制 :代码要求你跑1ms,但实际上跑了2ms,但是代码本身是正确的
    • 原因:逻辑中【求左树的高度】和【求右树的高度】都求了两次(判断求谁大谁小一次,算值求了一次),方式一不会出现该问题,因为都只各求了一次
  3. 时复:O(n)
    • 实际上是遍历的操作,每个结点都遍历到了,如果有n个结点,时间复杂度就是O(n)
  4. 时间复杂度 VS 真正的执行时间:两者不一定相等,像该题,方法一和二的时复相同,但方式二的执行时间实际会更长
//方式一
 public  int getHeight(TreeNode root) {
     if(root == null) {
         return 0;
     }
     int leftH = getHeight(root.left);
     int rightH = getHeight(root.right);

     return (leftH > rightH ? leftH :rightH) + 1;
 }

//方式二
 public  int getHeight2(TreeNode root) {
     if(root == null) {
         return 0;
     }

     return (getHeight2(root.left) > getHeight2(root.right) ?
             getHeight2(root.left) :getHeight2(root.right)) + 1;
 }

检测值为value的元素是否存在

  1. 思路:遍历整个二叉树,如果值为value就返回,遍历方式可以从“前/中/后/层序遍历”中任选其一,此处用的是【前序遍历】
 public TreeNode find(TreeNode root,int val) {
     if(root == null) return null;
     
     if(root.val == val) {
         return root;
     } 
     TreeNode leftL = find(root.left,val);
     if(leftL != null) {
         return leftL;
     }
     TreeNode leftLR = find(root.right,val);
     if(leftLR != null) {
         return leftLR;
     }
     return null;
 }

判断一棵树是不是完全二叉树

  1. 思路:创建出一个队列,遍历树并将结点放到队列里,当提出的队首元素为空时,停止遍历操作。然后遍历整个队列,如果队列里没有结点,全是null,说明这是一棵完全二叉树
public boolean isCompleteTree(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    if(root != null) {
        queue.offer(root);
    }
    while (!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        if(cur != null) {
            queue.offer(cur.left);
            queue.offer(cur.right);
        }else {
            break;
        }
    }
    while (!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        if(cur != null) {
            return false;
        }
    }
    return true;
}

在root这棵树当中 找到node这个节点上的位置

public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
    if(root == null) {
        return false;
    }
    stack.push(root);
    if(root == node) {
        return true;
    }
    boolean ret = getPath(root.left,node,stack);
    if(ret == true) {
        return true;
    }

    boolean ret2 = getPath(root.right,node,stack);
    if(ret2 == true) {
        return true;
    }
    stack.pop();
    return false;
}

求最大深度

 public int maxDepth(TreeNode root) {
     if(root == null) {
         return 0;
     }
     int leftH = maxDepth(root.left);
     int rightH = maxDepth(root.right);

     if(leftH >= 0 && rightH >= 0 &&
             Math.abs(leftH-rightH) <= 1) {
         return Math.max(leftH,rightH) + 1;
     }else {
         return -1;
     }
 }

2.3 二叉树练习

检查两棵树是否相同

  1. 代码链接
  2. 相同的判断:结构相同,里面的value值也相同
  3. 思路
    在这里插入图片描述
  4. 时间复杂度: O(min(m, n)),m和n分别为两棵树的节点个数
    • 因为,两棵树如果是不相同的情况下,一定会率先把一棵树遍历完
  5. 空间复杂度:O(min(m, n))
 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;
     }
     //此时 p 和 q 都不等于空
     if(p.val != q.val) {
         return false;
     }
     return isSameTree(p.left,q.left)
             && isSameTree(p.right,q.right);
 }

另一棵数的子树

  1. 代码链接

  2. 关于子树:两颗树一模一样,或者一棵树与另一棵树的一部分一模一样

  3. 思路
    (1)判断 root 和 subRoot 是不是两棵相同的树:isSameTree(root,subRoot)

    (2)判断root左树的子树是不是subRoot:isSubtree(root.left,subRoot)

    (3)判断root左树的子树是不是subRoot:isSubtree(root.right,subRoot)

    (4)如果遍历完毕,但是上述的三个条件都不满足,说明你给的根本就不是子树,返回false

  4. 为什么要判断 root 是否等于 null
    在这里插入图片描述

  5. 时间复杂度: O(r * s),r 和 s 分别为 root 和 subRoot 的节点个数

    • 理解:root上的每个点都需要和子树上的判断相不相同
 // 时间复杂度: O(min(m,n))
 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;
     }
     //一定是p 和 q 都不等于空!
     if(p.val != q.val) {
         return false;
     }
     return isSameTree(p.left,q.left)
             && isSameTree(p.right,q.right);
 }

 public boolean isSubtree(TreeNode root, TreeNode subRoot) {
     if(root == null) {
         return false;
     }
     if(isSameTree(root,subRoot)) {
         return true;
     }
     if(isSubtree(root.left,subRoot)) {
         return true;
     }
     if(isSubtree(root.right,subRoot)) {
         return true;
     }
     return false;
 }

翻转二叉树

  1. 代码链接
  2. 思路
    在这里插入图片描述
 public TreeNode invertTree(TreeNode root) {
     if(root == null) return null;

     TreeNode tmp = root.left;
     root.left = root.right;
     root.right = tmp;

     invertTree(root.left);
     invertTree(root.right);
     return root;
 }

是否是平衡二叉树

  1. 代码链接
  2. 思路:题目要求是所有子树的高度差不能超过1,而不是root的左右树高度差不大于1。那么就是执行遍历操作,每次遍历都计算左右树的高度,如果高度差>1,表示不是平衡二叉树。如果全部遍历完,高度一直都没大于1,那么就是平衡二叉树
  3. 方法一:时间复杂度为O(n * n),n为 root 的结点个数
    • 因为每个节点都要去求高度
 public boolean isBalanced(TreeNode root) {
     if(root == null) return true;

     int leftHight = getHeight(root.left);
     int rightHight = getHeight(root.right);

     return Math.abs(leftHight-rightHight) < 2
             && isBalanced(root.left)
             && isBalanced(root.right);
 }

 public  int getHeight(TreeNode root) {
     if(root == null) {
         return 0;
     }
     int leftH = getHeight(root.left);
     int rightH = getHeight(root.right);

     return (leftH > rightH ? leftH :rightH) + 1;
 }
  1. 方法二:优化了方法一中,多算了好几次高度的问题,将时间复杂度优化为O(N)
    • 在算高度的同时,每次都拿左边高度和右边高度比较一下,如果一旦不平衡了,返回一个负数。相当于本来只是在求root的高度,但是在求的过程中,发现子树已经不符合高度差不超过1的条件了,此时已经不平衡了
    • 如果有一个不平衡,会返回-1,后续因为无法通过【left >= 0和right >= 0】的条件,一直返回-1,所以只要最终判断看结果是否大于等于0即可
 public boolean isBalanced(TreeNode root) {
     if(root == null) return true;
     return maxDepth(root) >= 0;
 }

 public  int maxDepth(TreeNode root) {
     if(root == null) {
         return 0;
     }
     
     int leftH = maxDepth(root.left);
     int rightH = maxDepth(root.right);

 if (left >= 0 && right >= 0 && Math.abs(leftH - rightH) <= 1){
 return Math.max(leftH, rightH) + 1;
 }else {
 return -1;
 }
 }

对称二叉树

  1. 代码链接
 public boolean isSymmetric(TreeNode root) {
     if(root == null) return true;
     return isSymmetricChild(root.left,root.right);
 }
 
 public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
 //一个为空一个不为空
     if(leftTree == null && rightTree != null ||
             leftTree != null && rightTree == null ) {
         return false;
     }
     
     //两个都为空
     if(leftTree == null && rightTree == null) {
         return true;
     }
     
     //都不为空时,判断值
     if(leftTree.val != rightTree.val) {
         return false;
     }
     
     return isSymmetricChild(leftTree.left,rightTree.right)
             && isSymmetricChild(leftTree.right,rightTree.left);
 }

二叉树前序非递归遍历实现

  1. 代码链接
  2. 思路
    • 定义一个栈,用栈来模拟递归的过程,先一直取左边的点,只要不为空就放到栈里。当左树的点都放进去后,把栈顶的元素提出来,然后让cur来到该点的右边
    • 为什么会有 while (cur != null || !stack.empty()):当走到一个左右结点都无的叶子结点后,把栈顶元素提出来后,该元素的右结点依旧为null,此时如果没有该判断条件,无法让右边的结点也入栈
 public void preOrderNor(TreeNode root) {
     if(root == null) return;
     Stack<TreeNode> stack = new Stack<>();
     TreeNode cur = root;

     while (cur != null || !stack.empty()) {
         while (cur != null) {
             stack.push(cur);
             System.out.print(cur.val + " ");
             cur = cur.left;
         }
         
         //此时cur == null
         TreeNode top = stack.pop();
         cur = top.right;
     }
 }

二叉树中序非递归遍历实现

  1. 代码链接
  2. 思路:先把所有的结点加进来(把根保存起来),当cur为null才出栈,此处出的栈是最左边的节点
 public void inOrderNor(TreeNode root) {
     if(root == null) return;
     Stack<TreeNode> stack = new Stack<>();
     TreeNode cur = root;

     while (cur != null || !stack.empty()) {
         while (cur != null) {
             stack.push(cur);
             cur = cur.left;
         }
         //cur == null
         TreeNode top = stack.pop();
         System.out.print(top.val + " ");
         cur = top.right;
     }
 }

二叉树后序非递归遍历实现

  1. 代码链接
  2. 思路:遍历存结点,但是出线的时候用peek,如果该结点的右边没有结点就打印,如果有结点就根据peek的结果拿到右结点。为避免重复打印和死循环,需要用prev记录下已经被打印过的结点
 public void postOrderNor(TreeNode root) {
     if(root == null) return;
     Stack<TreeNode> stack = new Stack<>();
     TreeNode cur = root;
     TreeNode prev= null;
     while (cur != null || !stack.empty()) {
         while (cur != null) {
             stack.push(cur);
             cur = cur.left;
         }
         //cur == null
         TreeNode top = stack.peek();

         if(top.right == null || top.right == prev) {
             System.out.print(top.val+" ");
             prev = top;//记录下来当前的top已经被打印过了
             stack.pop();
         }else {
             cur = top.right;
         }
     }
 }

二叉树的构建和遍历

  1. 代码链接
  2. 思路
    • 使用i来遍历字符串,并构造结点
      • 题目根据前序遍历的方式给了个字符串,我们使用i来遍历的,如果是#,说明不是个结点,不是#说明是结点,需要构造
      • 因为题目给的是前序遍历的字符串,所以我们创建树的时候,也必须根据前序遍历的方式去创建
    • 为什么要把i定义在外面
      • 如果定义在里面,虽然i++了,但是递归之后,执行的逻辑里,i依旧是从0开始
    • 越界的情况
      • i不必要担心越界的情况,因为给的字符串是合理的,是能够构建出一个二叉树的
import java.util.Scanner;
//定义节点
class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inOrder(root);
        }
    }

    public static int i = 0;
    public static TreeNode createTree(String str) {

        TreeNode root = null;
        
        if(str.charAt(i) != '#') {

            root = new TreeNode(str.charAt(i));
            i++;

            root.left = createTree(str);
            root.right = createTree(str);

        }else {
            i++;
        }

        return root;
    }

    public static void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}

二叉树的最近公共祖先

  1. 代码链接
  2. 思路一:让二叉树的每个结点都有一个指向父亲的节点,这样就相当于在求【链表相交结点】。但该思路仅靠二叉树是无法实现的,我们还需要去借助【栈】
    • 操作
      • 我们可以把p和q的路径结点分别存到两个栈上,如果两个长度就不一样,就出掉长度更长的那个栈的结点,直到两个栈长度一样。
      • 当两个栈长度一样时,同时出栈,当出栈的元素一样,说明这个元素就是公共祖先
    • 如何把存路径结点:遍历这棵树,只要当前结点不等于p或q,就将其存到栈里,当一个结点左右两边都不包含p或q时,就将其从栈中拿出来,因为它根本不是路径上的值
 public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
     if(root == null) return null;

     Stack<TreeNode> s1 = new Stack<>();
     getPath(root,p,s1);

     Stack<TreeNode> s2 = new Stack<>();
     getPath(root,q,s2);

     int size1 = s1.size();
     int size2 = s2.size();

     if(size1 > size2) {
         int size = size1 - size2;
         while (size != 0) {
             s1.pop();
             size--;
         }
     }else {
         int size = size2 - size1;
         while (size != 0) {
             s2.pop();
             size--;
         }
     }
     //两个栈当中 的元素 是一样大小的
     while (!s1.empty() && !s2.empty()) {
         TreeNode tmp1 = s1.pop();
         TreeNode tmp2 = s2.pop();
         if(tmp1 == tmp2) {
             return tmp1;
         }
     }
     return null;
 }

  public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
      if(root == null) {
          return false;
      }
      stack.push(root);
      if(root == node) { //找到这个结点了,返回true
          return true;
      }

  //去root左树这边去找node这个结点,找到后放到栈里
      boolean ret = getPath(root.left,node,stack);
      if(ret == true) { //此时在子树的左边已经找到了,就不需要再继续找node了,直接返回true
          return true;
      }

      boolean ret2 = getPath(root.right,node,stack);
      if(ret2 == true) {  //此时在左边已经找到了,就不需要再继续找
          return true; 
      }
      stack.pop(); //当前这个节点的左右两边都没有我们想要的,出栈+return false
      return false;
  }
  1. 思路二

在这里插入图片描述

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) return null;

    if(p == root || q == root) {  //情况1
        return root;
    }

//分别到左右树去找q和p,如果是情况2,那么leftRet和rightRet都会有值
//如果是情况3,那么leftRet会是离root最近的值
//如果是情况4,那么rightRet会是离root最近的值
    TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
    TreeNode rightRet = lowestCommonAncestor(root.right,p,q);

    if(leftRet != null && rightRet != null) {  
        return root;  //情况2
    }else if(leftRet != null) {
        return leftRet;  //情况3
    }else {
        return rightRet;  //情况4
    }
}

根据二叉树创建字符串

  1. 代码链接
class Solution {
    public String tree2str(TreeNode root) {
        if (root == null) return null;

        StringBuilder StringBuilder = new StringBuilder();

        tree2strChild(root, StringBuilder);

        return StringBuilder.toString();
    }

    private void tree2strChild(TreeNode t, StringBuilder stringBuilder){
        if (t == null) return;

        stringBuilder.append(t.val);

        if (t.left != null){
            stringBuilder.append("(");
            tree2strChild(t.left, stringBuilder);
            stringBuilder.append(")");
        }else{
            if (t.right == null){
                return;
            }else{
                stringBuilder.append("()");
            }
        }

        if (t.right != null){
            stringBuilder.append("(");
            tree2strChild(t.right, stringBuilder);
            stringBuilder.append(")");
        }else{
            return;
        }
    }
}

根据一棵树的前序遍历与中序遍历构造二叉树

  1. 代码链接
  2. 思路
    在这里插入图片描述
  3. 解析
    • 递归的出口:if(inbegin > inend) ,代表该结点的左边和右边都没有结点
    • findIndex:在中序遍历中去找关键词key
    • 将preIndex提取为成员变量,而不是方法里的局部变量:为了保证preIndex的累加效果(不让递归回去之后,preIndex也回退了)
class Solution {
public int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    
    private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
        if(inbegin > inend) {
            return null;
        }
        //先创建根节点
        TreeNode root = new TreeNode(preorder[preIndex]);//根节点

        //找到根节点 所在中序遍历中的位置
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
        preIndex++;
        // 先创建左树 再创建右树   本身是在遍历: 前序遍历
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);

        return root;
    }

    private int findIndex(int[] inorder,int inbegin,int inend,int key) {
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}

根据一棵树的中序遍历与后序遍历构造二叉树

  1. 代码链接
  2. 思路
    在这里插入图片描述
class Solution {
    public int postIndex = 0;


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

        postIndex = postorder.length-1;

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


    private TreeNode buildTreeChild(int[] postorder, int[] inorder,int inbegin,int inend) {
        //递归的出口  不满足这个条件 那么就是没有了左树 或者右树
        if(inbegin > inend) {
            return null;
        }
        //先创建根节点
        TreeNode root = new TreeNode(postorder[postIndex]);//根节点

        //找到根节点 所在中序遍历中的位置
        int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
        postIndex--;
        
        // 先创建右树    再创建左树   本身是在遍历: 后序遍历
        root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
        root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);

        return root;
    }

    private int findIndex(int[] inorder,int inbegin,int inend,int key) {
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}

原文地址:https://blog.csdn.net/wuweixiaoyue/article/details/142437940

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!