树与二叉树数据结构详解

转x33g5p2x  于2022-01-13 转载在 其他  
字(19.6k)|赞(0)|评价(0)|浏览(464)

一、树的基本概念

1.树的知识框架

1.树的定义

树是n（n>=0）个结点的有限集。当n = 0时，称为空树。在任意一棵非空树中应满足：

  1. 有且仅有一个特定的称为根的结点。
  2. 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

显然，树的定义是递归的，即在树的定义中又用到了自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

  1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
  2. 树中所有结点可以有零个或多个后继。

因此n个结点的树中有n-1条边。

3.树的基本术语

结合图示来说明一下树的一些基本术语和概念。

  1. 考虑结点K。根A到结点K的唯一路径上的任意结点,称为结点K的祖先。如结点B是结点K的祖先,而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲,而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟,如结点K和结点L有相同的双亲E,即K和L为兄弟。
  2. 树中其中某个结点的孩子个数称为该结点的度,树中结点的最大度数称为树的度。如结点B的度为2,结点D的度为3（此结点度最大），树的度为3。
  3. 度大于0的结点称为分支结点(又称非终端结点);度为0(没有孩子结点)的结点称为叶子结点(又称终端结点)。在分支结点中,每个结点的分支数就是该结点的度。
  4. 结点的深度、高度和层次。
    结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。双亲在同一层的结点互为堂兄弟,图中结点G与E,F,H,I,J互为堂兄弟。
    结点的深度是从根结点开始自顶向下逐层累加的。它可以是某一层，例如结点F所在的深度为3，而L结点所在的深度为4。
    结点的高度是从叶结点开始自底向上逐层累加的。高度只讲的是树的高度，树的高度为4。
    树的高度(或深度)是树中结点的最大层数。图中树的高度为4。
  5. 有序树和无序树。**树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。**假设图为有序树,若将子结点位置互换,则变成一棵不同的树。
  6. 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。
    注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。
  7. 森林。森林是m (m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。一棵树也可以称作一个森林。

4.树的性质

二叉树的性质

注意其中两个性质：
1、

其中这两个性质是可以互相转化的，只要记住其中一个性质就行。

2、

这个性质可以推为：
1.已经父亲结点的下标为i，则其左孩子的结点为2i+1，右孩子的结点为2i+2。
2.已知孩子结点n，推父亲节点：(n-1)/2 。

面试题：

比如：假设一棵完全二叉树中总共有1000个节点，则该二叉树中多少个叶子节点，多少个非叶子节点，多少个节点只有左孩子，多少个节点只有右孩子。

答：因为该二叉树是一棵完全二叉树，所以不可能有结点是只有右孩子的，因此最后一个空为0。

再求出该二叉树一共有多少层，因为有1000个结点，又由log2的（n+1）向上取整得深度为10，但是第十层还没放满（放满的结点数为2的10次方-1）。我们还可以求出10层前的结点一共有多少个，由2的9次方-1得511，所以第十层放的是1000-511=489个结点。

因此第十层的489个结点都为叶子结点，但是不要忘了第十层是未放满的，因此推出第九层中也是有叶子结点的。将第十层的叶子结点除2，得第9层的非叶子结点为：489/2=244.5，说明有第九层非叶子结点中有一个结点是只有左节点的。第九层结点个数：2的（9-1）次方=256个。因此非叶子结点有245个。求得第九层的叶子结点为256-245=11个。所以一共加起来的叶子结点有11+489=500个。

又因为二叉树的结点数是由叶子结点和非叶子结点组成的，所以非叶子结点有1000-500==500个，叶子结点有500个，只有左孩子的只有1个，没有只有右孩子的结点。

5.树的存储结构

二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：

  1. // 孩子表示法
  2. class Node {
  3.  int val; // 数据域
  4.  Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
  5.  Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
  6. }
  7. // 孩子双亲表示法
  8. class Node {
  9.  int val; // 数据域
  10.  Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
  11.  Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
  12.  Node parent; // 当前节点的根节点
  13. }

其实二叉树如何表示，主要是看创建的TreeNode结点类是如何设置来存储二叉树中的结点的。不过大多数情况下都是采取孩子表示法来构建二叉树。

二、二叉树的操作

1.二叉树的遍历

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。

在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：

二叉树的遍历分为：
1.NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树。
2.LNR：中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。
3.LRN：后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

2.二叉树的基本操作

  1. import java.util.*;
  3. class TreeNode {
  4.     public char val;
  5.     public TreeNode left;
  6.     public TreeNode right;
  8.     public TreeNode(char val) {
  9.         this.val = val;
  10.     }
  11. }
  12. public class BinaryTree {
  13.     public TreeNode creatTree() {
  14.         TreeNode A = new TreeNode('A');
  15.         TreeNode B = new TreeNode('B');
  16.         TreeNode C = new TreeNode('C');
  17.         TreeNode D = new TreeNode('D');
  18.         TreeNode E = new TreeNode('E');
  19.         TreeNode F = new TreeNode('F');
  20.         TreeNode G = new TreeNode('G');
  21.         TreeNode H = new TreeNode('H');
  22.         A.left = B;
  23.         B.left = D;
  24.         B.right = E;
  25.         E.right = H;
  26.         A.right = C;
  27.         C.left = F;
  28.         C.right = G;
  29.         return A;
  30.     }
  32.     // 前序遍历
  33.     void preOrderTraversal(TreeNode root) {
  34.         if (root == null) {
  35.             return;
  36.         }
  37.         System.out.print(root.val + " ");
  38.         preOrderTraversal(root.left);
  39.         preOrderTraversal(root.right);
  40.     }
  42.     // 中序遍历
  43.     void inOrderTraversal(TreeNode root) {
  44.         if (root == null) {
  45.             return;
  46.         }
  47.         inOrderTraversal(root.left);
  48.         System.out.print(root.val + " ");
  49.         inOrderTraversal(root.right);
  50.     }
  52.     // 后序遍历
  53.     void postOrderTraversal(TreeNode root) {
  54.         if (root == null) {
  55.             return;
  56.         }
  57.         postOrderTraversal(root.left);
  58.         postOrderTraversal(root.right);
  59.         System.out.print(root.val + " ");
  60.     }
  62.     // 遍历思路-求结点个数
  63.     static int size = 0;
  65.     void getSize1(TreeNode root) {
  66.         if (root == null) {
  67.             return;
  68.         }
  69.         getSize1(root.left);
  70.         getSize1(root.right);
  71.         size++;
  72.     }
  74.     // 子问题思路-求结点个数
  75.     int getSize2(TreeNode root) {
  76.         if (root == null) {
  77.             return 0;
  78.         }
  79.         return getSize2(root.left) + getSize2(root.right) + 1;
  80.     }
  82.     // 遍历思路-求叶子结点个数
  83.     static int leafSize = 0;
  85.     void getLeafSize1(TreeNode root) {
  86.         if (root == null) {
  87.             return;
  88.         }
  89.         if (root.left == null && root.right == null) {
  90.             leafSize++;
  91.         }
  92.         getLeafSize1(root.left);
  93.         getLeafSize1(root.right);
  94.     }
  96.     // 子问题思路-求叶子结点个数
  97.     int getLeafSize2(TreeNode root) {
  98.         if (root == null) {
  99.             return 0;
  100.         }
  101.         if (root.left == null && root.right == null) {
  102.             return 1;
  103.         }
  104.         return getLeafSize2(root.left) + getLeafSize2(root.right);
  105.     }
  107.     // 子问题思路-求第 k 层结点个数
  108.     int getKLevelSize(TreeNode root, int k) {
  109.         if (root == null) {
  110.             return 0;
  111.         }
  112.         if (k == 1) {
  113.             return 1;
  114.         }
  115.         return getKLevelSize(root.left, k - 1) + getKLevelSize(root.right, k - 1);
  116.     }
  118.     // 获取二叉树的高度
  119.     int getHeight(TreeNode root) {
  120.         if (root == null) {
  121.             return 0;
  122.         }
  123.         int leftNode = getHeight(root.left);
  124.         int rightNode = getHeight(root.right);
  125.         return Math.max(rightNode, leftNode) + 1;
  126.     }
  128.     // 查找 val 所在结点，没有找到返回 null
  129. // 按照 根 -> 左子树 -> 右子树的顺序进行查找
  130. // 一旦找到，立即返回，不需要继续在其他位置查找
  131.     TreeNode find(TreeNode root, char val) {
  132.         if (root == null) {
  133.             return null;
  134.         }
  135.         if (root.val == val) {
  136.             return root;
  137.         }
  138.         TreeNode ret = find(root.left, val);
  139.         if (ret != null) {
  140.             return ret;
  141.         }
  142.         ret = find(root.right, val);
  143.         if (ret != null) {
  144.             return ret;
  145.         }
  146.         return null;
  147.     }
  149.     // 层序遍历
  150.     void levelOrderTraversal(TreeNode root) {
  151.         if (root == null) {
  152.             return;
  153.         }
  154.         Queue<TreeNode> queue = new LinkedList<>();
  155.         queue.offer(root);
  156.         while (!queue.isEmpty()) {
  157.             TreeNode top = queue.poll();
  158.             System.out.print(top.val + " ");
  159.             if (top.left != null) {
  160.                 queue.offer(top.left);
  161.             }
  162.             if (top.right != null) {
  163.                 queue.offer(top.right);
  164.             }
  165.         }
  166.         System.out.println();
  167.     }
  168.     //层序遍历
  169.     public List<List<Character>> levelOrder(TreeNode root) {
  170.         List<List<Character>> list = new ArrayList<>();
  171.         if (root == null) {
  172.             return list;
  173.         }
  174.         Queue<TreeNode> queue = new LinkedList<>();
  175.         queue.offer(root);
  176.         while (!queue.isEmpty()) {
  177.             List<Character> list1 = new ArrayList<>();
  178.             int size = queue.size();
  179.             while (size != 0) {
  180.                 TreeNode top = queue.poll();
  181.                 list1.add(top.val);
  182.                 if (top.left != null) {
  183.                     queue.add(top.left);
  184.                 }
  185.                 if (top.right != null) {
  186.                     queue.add(top.right);
  187.                 }
  188.                 size--;
  189.             }
  190.             list.add(list1);
  191.         }
  192.         return list;
  193.     }
  195.     // 判断一棵树是不是完全二叉树
  196.     boolean isCompleteTree(TreeNode root) {
  197.         if (root == null) {
  198.             return true;
  199.         }
  200.         Queue<TreeNode> queue = new LinkedList<>();
  201.         queue.offer(root);
  202.         while (!queue.isEmpty()) {
  203.             TreeNode top = queue.poll();
  204.             if (top != null) {
  205.                 queue.offer(top.left);
  206.                 queue.offer(top.right);
  207.             } else {
  208.                 break;
  209.             }
  210.         }
  211.         while(!queue.isEmpty()) {
  212.             TreeNode cur = queue.peek();
  213.             if(cur==null) {
  214.                 queue.poll();
  215.             }else {
  216.                 return false;
  217.             }
  218.         }
  219.         return true;
  220.     }
  222.     //求二叉树的左视图
  223.     public void leftScenery(TreeNode root) {
  224.         if(root==null) {
  225.             return ;
  226.         }
  227.         List<List<TreeNode>> list = new LinkedList<>();
  228.         Queue<TreeNode> queue = new LinkedList<>();
  229.         queue.offer(root);
  230.         while(!queue.isEmpty()) {
  231.             List<TreeNode> list1 = new LinkedList<>();
  232.             int size = queue.size();
  233.             while(size!=0) {
  234.                 TreeNode top = queue.poll();
  235.                 list1.add(top);
  236.                 if(top.left!=null) {
  237.                     queue.offer(top.left);
  238.                 }
  239.                 if(top.right!=null) {
  240.                     queue.offer(top.right);
  241.                 }
  242.                 size--;
  243.             }
  244.             list.add(list1);
  245.         }
  246.         for (List<TreeNode> e:list) {
  247.             for (TreeNode p: e) {
  248.                 System.out.print(p.val+" ");
  249.                 break;
  250.             }
  251.         }
  252.     }
  254.     //二叉树的非递归先序遍历
  255.     public void preOrderTraversalNot(TreeNode root) {
  256.         if(root==null) {
  257.             return;
  258.         }
  259.         TreeNode cur = root;
  260.         Stack<TreeNode> stack = new Stack<>();
  261.         while(cur!=null||!stack.empty()) {
  262.             while(cur!=null) {
  263.                 stack.push(cur);
  264.                 System.out.print(cur.val+" ");
  265.                 cur=cur.left;
  266.             }
  267.             TreeNode top = stack.pop();
  268.             cur=top.right;
  269.         }
  270.     }
  272.     // 中序遍历
  273.     public void inOrderTraversalNot(TreeNode root) {
  274.         if(root==null) {
  275.             return;
  276.         }
  277.         TreeNode cur = root;
  278.         Stack<TreeNode> stack = new Stack<>();
  279.         while(cur!=null||!stack.empty()) {
  280.             while(cur!=null) {
  281.                 stack.push(cur);
  282.                 cur=cur.left;
  283.             }
  284.             TreeNode top = stack.pop();
  285.             System.out.print(top.val+" ");
  286.             cur=top.right;
  287.         }
  288.     }
  290.     // 后序遍历非递归
  291.     public void postOrderTraversalNot(TreeNode root) {
  292.         if(root==null) {
  293.             return;
  294.         }
  295.         Stack<TreeNode> stack = new Stack<>();
  296.         TreeNode cur = root;
  297.         TreeNode pre = null;
  298.         while(cur!=null||!stack.empty()) {
  299.             while(cur!=null) {
  300.                 stack.push(cur);
  301.                 cur=cur.left;
  302.             }
  303.             cur=stack.peek();
  304.             if(cur.right==null||cur.right==pre) {
  305.                 TreeNode top = stack.pop();
  306.                 System.out.print(top.val+" ");
  307.                 pre=cur;
  308.                 cur=null;
  309.             }else {
  310.                 cur=cur.right;
  311.             }
  312.         }
  313.     }
  314. }

三、基础面试题

1.二叉树的前序遍历

对应leetcode题

思路1：递归：注意此题的返回值为List< Integer >，因此首先要创建一个该类型的list，不过结点有可能为空，则直接返回空的list。为了能够使用到方法的返回值，我们在进行递归的时候可以利用list的addAll方法将左和右递归所添加到新的list1和list2当中的数字。

  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> list = new ArrayList<>();
  4.         if(root==null) {
  5.             return list;
  6.         }
  7.         list.add(root.val);
  8.         List<Integer> list1 = preorderTraversal(root.left);
  9.         list.addAll(list1);
  10.         List<Integer> list2 = preorderTraversal(root.right);
  11.         list.addAll(list2);
  12.         return list;
  13.     }
  14. }

思路2：迭代：我们可以用栈来实现。先创建好list，判断root是否为空，为空则直接返回list；不为空则将root的元素添加到stack中。先直接让root到其二叉树的最左结点，如果一直不为空依次将经过的元素添加到栈当中。当root已经为空，则将top栈顶元素出栈，并且让root结点指向top结点的右子树。最外层循环的判断条件为root不为空和栈不为空。

  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> list = new ArrayList<>();
  4.         if(root==null) {
  5.             return list;
  6.         }
  7.         Stack<TreeNode> stack = new Stack<>();
  8.         TreeNode cur = root;
  9.         while(cur!=null||!stack.empty()) {
  10.             while(cur!=null) {
  11.                 stack.push(cur);
  12.                 list.add(cur.val);
  13.                 cur=cur.left;
  14.             }
  15.             TreeNode top = stack.pop();
  16.             cur=top.right;
  17.         }
  18.         return list;
  19.     }
  20. }

2.二叉树的中序遍历

对应leetcode题
思路：和前序遍历的思路差不多。

代码一：递归

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> list = new ArrayList<>();
  4.         if(root==null) {
  5.             return list;
  6.         }
  7.         List<Integer> list1 = inorderTraversal(root.left);
  8.         list.addAll(list1);
  9.         list.add(root.val);
  10.         List<Integer> list2 = inorderTraversal(root.right);
  11.         list.addAll(list2);
  12.         return list;
  13.     }
  14. }

代码二：迭代

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> list = new ArrayList<>();
  4.         if(root==null) {
  5.             return list;
  6.         }
  7.         Stack<TreeNode> stack = new Stack<>();
  8.         while(root!=null||!stack.empty()) {
  9.             while(root!=null) {
  10.                 stack.push(root);
  11.                 root=root.left;
  12.             }
  13.             TreeNode top = stack.pop();
  14.             list.add(top.val);
  15.             root=top.right;
  16.         }
  17.         return list;
  18.     }
  19. }

3.二叉树的后序遍历

对应leetcode题

代码1：递归

  1. class Solution {
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> list = new ArrayList<>();
  4.         if(root==null) {
  5.             return list;
  6.         }
  7.         List<Integer> list1 = postorderTraversal(root.left);
  8.         list.addAll(list1);
  9.         List<Integer> list2 = postorderTraversal(root.right);
  10.         list.addAll(list2);
  11.         list.add(root.val);
  12.         return list;
  13.     }
  14. }

代码2:迭代

思路：后序遍历的迭代跟前序和中序遍历的迭代不相同。因为后序遍历的顺序为左->右->根 。因此在root到达最左边时，不能急于直接将top栈顶元素出栈，而是当左树为空时将root变为栈顶元素，要判断该位置的右边是否为空和当右数不为空当出栈的元素为B时，它还会再次去循环上次的操作，会一直在B和E中死循环。具体可以下面这个例子来看。

当B右树不为空，则可以设置一个prev来标记。先将栈顶元素出栈，出栈的为E，则将E的值存起来，prev指向现在的cur结点处，即E。并且将cur置为空，避免了结点在B和E处的死循环。当然，如果右树为空的情况下，也可以是上面相同的操作，只不过是将两个操作步骤合并在一起。

  1. class Solution {
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<Integer>();
  4.         if (root == null) {
  5.             return res;
  6.         }
  7.         TreeNode cur = root;
  8.         Stack<TreeNode> stack = new Stack<TreeNode>();
  9.         TreeNode prev = null;
  10.         while (cur != null || !stack.empty()) {
  11.             while (cur != null) {
  12.                 stack.push(cur);
  13.                 cur = cur.left;
  14.             }
  15.             cur = stack.peek();
  16.             if (cur.right == null || cur.right == prev) {
  17.                 stack.pop();
  18.                 res.add(cur.val);
  19.                 prev = cur;
  20.                 cur = null;
  21.             } else {
  22.                 cur = cur.right;
  23.             }
  24.         }
  25.         return res;
  26.     }
  27. }

4.检查两颗树是否相同

对应leetcode题

主要有三种情况：
第一：当两棵树的根均为空，则相同；
第二：当两棵树其中一个根为空，则不同；
第三：判断两棵树的根结点的值是否相同，不同则返回false

每一个子树都是相同的判断方法，因此只要将两棵树的左树对比、右树对比即可。

  1. class Solution {
  2.     public boolean isSameTree(TreeNode p, TreeNode q) {
  3.         if(p==null&&q==null) {
  4.             return true;
  5.         }
  6.         if(p==null||q==null) {
  7.             return false;
  8.         }
  9.         if(p.val!=q.val) {
  10.             return false;
  11.         }
  12.         return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
  13.     }
  14. }

5.另一颗树的子树

对应leetcode题

思路：在第四题判断两棵树是否相同的基础上来判断另一棵树是否是子树的问题。无非就是在该树的左树与另一棵树作对比，如果相同则返回true，若false则判断该树的右数是否有另一棵树，有则返回true；到最后判断了左树和右树都没有该子树，则返回false。

  1. class Solution {
  2.     public boolean isSametree(TreeNode p,TreeNode q) {
  3.         if(p==null&&q==null) {
  4.             return true;
  5.         }
  6.         if(p==null||q==null) {
  7.             return false;
  8.         }
  9.         if(p.val!=q.val) {
  10.             return false;
  11.         }
  12.         return isSametree(p.left,q.left)&&isSametree(p.right,q.right);
  13.     }
  14.     public boolean isSubtree(TreeNode root, TreeNode subRoot) {
  15.         if(root==null&&subRoot==null) {
  16.             return true;
  17.         }
  18.         if(root==null||subRoot==null) {
  19.             return false;
  20.         }
  21.         if(isSametree(root,subRoot)) {
  22.             return true;
  23.         }
  24.         if(isSubtree(root.left,subRoot)) {
  25.             return true;
  26.         }
  27.         if(isSubtree(root.right,subRoot)) {
  28.             return true;
  29.         }
  30.         return false;
  31.     }
  32. }

6.二叉树最大深度

思路：求左树的高度后，再求右树的高度，最后取其中最高的高度的树加上根的那一个高度则为整棵二叉树的高度。

  1. class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.         if(root==null) {
  4.             return 0;
  5.         }
  6.         int leftDepth = maxDepth(root.left);
  7.         int rightDepth = maxDepth(root.right);
  8.         return (leftDepth>rightDepth)?(leftDepth+1):(rightDepth+1);
  9.     }
  10. }

注意：一定要创建leftDepth和rightDepth变量来记录左右子树的高度，不要在三目运算符当中用直接递归来判断，否则会用到多次递归，时间复杂度高。

7.判断一颗二叉树是否是平衡二叉树

对应leetcode题
平衡二叉树条件：如果一棵树是平衡二叉树，那么它的子树均是平衡二叉树。平衡二叉树的定义：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

此题有两种思路。分别是向下递归O(N^2)和向上递归O(N)。

向下递归：
思路：首先从根开始判断，如果从根开始就不满足一棵平衡二叉树的定义（判断左树的高度和右树高度相减的绝对值是否小于2。），那么此树一定不是一棵平衡二叉树。满足则递归它的左右子树，并且是一样的判断方法。

总结：
1.求当前根的左树和右树的高度，计算相减后的绝对值。
2.如果相减后的绝对值没有超过2，只能暂时证明此树是平衡的。
3.继续判断根的左树和右树。

  1. class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.         if(root==null) {
  4.             return 0;
  5.         }
  6.         int leftHeight=maxDepth(root.left);
  7.         int rightHeight=maxDepth(root.right);
  8.         return Math.max(leftHeight,rightHeight)+1;
  9.     }
  10.     public boolean isBalanced(TreeNode root) {
  11.         if(root==null) {
  12.             return true;
  13.         }
  14.         int leftHeight = maxDepth(root.left);
  15.         int rightHeight = maxDepth(root.right);
  16.         return 
  17.         Math.abs(leftHeight-rightHeight)<2 &&isBalanced(root.left)&&isBalanced(root.right);
  18.     }
  19. }

向上递归：

思路：在Depth方法内部，由int leftDepth = Depth(root.left);递归到了树的最左结点并求出该结点的左树高度。再由int rightDepth = Depth(root.right);计算到了它右树的高度。最左结点的左树和右树一定为空，则加上该结点它的高度为1。以此类推，如果其中有一棵子树的左树和右树的高度差大于等于2，则整棵树一定不是一棵平衡二叉树，直接返回-1。因此在isBalanced方法里面直接判断最后的返回值是否大于等于0即可，为负则不是平衡二叉树。

  1. class Solution {
  2.     public int Depth(TreeNode root) {
  3.         if(root==null) {
  4.             return 0;
  5.         }
  6.         int leftDepth = Depth(root.left);
  7.         int rightDepth = Depth(root.right);
  8.         if(leftDepth>=0&&rightDepth>=0&&Math.abs(leftDepth-rightDepth)<2) {
  9.             return (leftDepth>rightDepth)?(leftDepth+1):(rightDepth+1);
  10.         }else {
  11.             return -1;
  12.         }
  13.     }
  14.     public boolean isBalanced(TreeNode root) {
  15.         if(root==null) {
  16.             return true;
  17.         }
  18.         return Depth(root)>=0;
  19.     }
  20. }

8.对称二叉树

对应leetcode题
思路跟判断两棵树是否相等相似，只不过此处换为判断子树的左子树的左和右子树的右、左子树的右和右子的左是否相等。

  1. class Solution {
  2.     public boolean isSametree(TreeNode p,TreeNode q) {
  3.         if(p==null&&q==null) {
  4.             return true;
  5.         }
  6.         if(p==null||q==null) {
  7.             return false;
  8.         }
  9.         if(p.val!=q.val) {
  10.             return false;
  11.         }
  12.         return isSametree(p.left,q.right)&&isSametree(p.right,q.left);
  13.     }
  14.     public boolean isSymmetric(TreeNode root) {
  15.         if(root==null) {
  16.             return true;
  17.         }
  18.         return isSametree(root.left,root.right);
  19.     }
  20. }

9.二叉树的镜像

对应leetcode题

思路：要将二叉树的结点进行交换，不要交换结点的值。再根处交换完左结点和右结点后，依次递归下去进行相同的步骤，并且交换后左右子树都要进行结点交换。

  1. public class Solution {
  2.     public TreeNode convert(TreeNode pCur) {
  3.         if(pCur==null) {
  4.             return null;
  5.         }
  6.         if(pCur.left==null&&pCur.right==null) {
  7.             return pCur;
  8.         }
  9.         TreeNode tmp = pCur.left;
  10.         pCur.left=pCur.right;
  11.         pCur.right=tmp;
  12.         convert(pCur.left);
  13.         convert(pCur.right);
  14.         return pCur;
  15.     }
  16.     public TreeNode Mirror (TreeNode pRoot) {
  17.         // write code here
  18.         if(pRoot==null) {
  19.             return null;
  20.         }
  21.         if(pRoot.left==null&&pRoot.right==null) {
  22.             return pRoot;
  23.         }
  24.         TreeNode root = convert(pRoot);
  25.         return root;
  26.     }
  27. }

四、进阶面试题

1.二叉树的构建及遍历

思路：根据先序遍历的字符串来构建出二叉树，再进行中序遍历来输出遍历结果。无非就是先根据先序遍历来一个个创建结点串联起来，并且用i来遍历字符串。
对应leetcode题
注：是一个ACM模式的题

  1. import java.util.Scanner;
  2. class TreeNode {
  3.     public char val ;
  4.     public TreeNode left;
  5.     public TreeNode right;
  6.     
  7.     public TreeNode(char val) {
  8.         this.val=val;
  9.     }
  10. }
  12. public class Main {
  13.     public static int i = 0 ;
  14.     public static TreeNode inorderChild(String str) {
  15.         if(str==null) {
  16.             return null;
  17.         }
  18.         char ch = str.charAt(i);
  19.         TreeNode root = null;
  20.         if(ch!='#') {
  21.             root = new TreeNode(ch);
  22.             i++;
  23.             root.left=inorderChild(str);
  24.             root.right=inorderChild(str);
  25.         }else {
  26.             i++;
  27.         }
  28.         return root;
  29.     }
  30.     public static void inorder(TreeNode root) {
  31.         if(root==null) {
  32.             return ;
  33.         }
  34.         inorder(root.left);
  35.         System.out.print(root.val+" ");
  36.         inorder(root.right);
  37.     }
  38.     public static void main(String[] args) {
  39.         Scanner scan = new Scanner(System.in);
  40.         String str = scan.nextLine();
  41.         TreeNode root = inorderChild(str);
  42.         inorder(root);
  43.     }
  44. }

2.二叉树的分层遍历

对应leetcode题

思路：因为此题的返回类型为List<List< Integer >>，那么我们就首先要对它进行创建list。如果root为空就直接返回。此题要用到队列，到此处后先将root入队，再将root出队后将其左右子树的根入队，除非左结点或者右节点为空不入队。又因为每一层的结点都要保存到List< Integer >类型的list1变量中。因此还要有一个while循环依次将每一层的元素入到List< Integer >类型的变量中。最外层循环判断条件为队列不为空，每一层循环结束后都要将list1加入到list当中。

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         List<List<Integer>> list = new ArrayList<>();
  4.         if(root==null) {
  5.             return list;
  6.         }
  7.         Queue<TreeNode> queue = new LinkedList<>();
  8.         queue.offer(root);
  9.         while(!queue.isEmpty()) {
  10.             List<Integer> list1 = new ArrayList<>();
  11.             int size = queue.size();
  12.             while(size!=0) {
  13.                 TreeNode top = queue.poll();
  14.                 list1.add(top.val);
  15.                 if(top.left!=null) {
  16.                    queue.offer(top.left);
  17.                 }
  18.                 if(top.right!=null) {
  19.                    queue.offer(top.right);
  20.                 }
  21.                 size--;
  22.             }
  23.             list.add(list1);
  24.         }
  25.         return list;
  26.     }
  27. }

3.给定一个二叉树, 找到该树中两个指定节点的最近公共祖先（LCA问题）

对应leetcode题

思路：
情况1：
左右子树都有p和q，则它们的最近公共祖先就是root。

情况2：
因为此题用递归，如果p和q都在根结点的左树中，则哪个先找到的就直接返回，并且作为它们的公共祖先。直接返回root。

情况3：如果p和q都在根的右树，则判断方法跟情况1相同，哪个先找到的就直接返回root。

  1. class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if(root==null) {
  4.             return null;
  5.         }
  6.         if(root.val==p.val||root.val==q.val) {
  7.             return root;
  8.         }
  9.         TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
  10.         TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
  11.         if(leftNode!=null&&rightNode!=null) {//左右树都有p和q
  12.             return root;
  13.         }
  14.         if(leftNode!=null) {//在左树先找到的，右树找不到的，情况2
  15.             return leftNode;
  16.         }
  17.         if(rightNode!=null) {//在右树找不到，左树找到，情况3
  18.             return rightNode;
  19.         }
  20.         return null;//都不满足返回空，即没有p和q
  21.     }
  22. }

4.二叉树搜索树转换成排序双向链表

对应leetcode题

搜索二叉树特点：
1.若它的左子树不为空，则左子树上所有结点的值都小于根结点。
2.若它的右子树不为空，则左子树上所有结点的值都大于根结点。
3.它的左右子树分别为二叉搜索树。
4.二叉搜索树的中序遍历是有序的。

思路：先遍历到二叉树的最左结点，另每个结点的左子树指向前一个结点，右子树指向后一个结点。此处要设置prev来指向前驱结点。若prev不为空，prev的右子树指向pCur，并且让prev指向pCur，再去处理pCur的右子树。也是相同的处理方式，则采用递归。

  1. public class Solution {
  2.     public TreeNode prev = null;
  3.     public TreeNode convertTree(TreeNode pCur) {
  4.         if(pCur==null) {
  5.             return null;
  6.         }
  7.         convertTree(pCur.left);
  8.         pCur.left = prev;
  9.         if(prev!=null) {
  10.             prev.right=pCur;
  11.         }
  12.         prev=pCur;
  13.         convertTree(pCur.right);
  14.         return pCur;
  15.     }
  16.     public TreeNode Convert(TreeNode pRootOfTree) {
  17.         if(pRootOfTree==null) {
  18.             return null;
  19.         }
  20.         TreeNode root = convertTree(pRootOfTree);
  21.         while(root.left!=null) {
  22.             root=root.left;
  23.         }
  24.         return root;
  25.     }
  26. }

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

对应leetcode题

思路：根据前序遍历，可以确定整棵树的根为哪一个结点，就直接先创建好该结点。因为根可以在中序遍历中分为两部分，中序遍历的根的左边是根的左树，右边是根的右树。因此要先找到根在中序遍历的哪个位置。

但是要注意一个点。因为在根的左树中，每次递归下去会有rootIndex-1，inend不断减小；在根的右子树中，有rootIndex+1inbegin不断增大。因此会有inbegin>inend的情况，因此用此条件作为递归的结束条件。

  1. class Solution {
  2.     public int preIndex = 0 ;
  3.     public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {
  4.         if(inbegin>inend) {
  5.             return null;
  6.         }
  7.         TreeNode root = new TreeNode(preorder[preIndex]);
  8.         int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
  9.         preIndex++;
  10.         root.left=buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
  11.         root.right=buildTreeChild(preorder,inorder,rootIndex+1,inend);
  12.         return root;
  13.     }
  14.     public int findIndex(int[] inorder,int inbegin,int inend,int key) {
  15.         for(int i=0;i<=inend;i++) {
  16.             if(inorder[i]==key) {
  17.                 return i;
  18.             }
  19.         }
  20.         return -1;
  21.     }
  22.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  23.         if(preorder==null||inorder==null) {
  24.             return null;
  25.         }
  26.         TreeNode root = buildTreeChild(preorder,inorder,0,inorder.length-1);
  27.         return root;
  28.     }
  29. }

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

对应leetcode题

  1. class Solution {
  2.     public int postIndex = 0 ;
  3.     public TreeNode buildTreeChild(int[] inorder,int inbegin,int inend,int[] postorder) {
  4.         if(inbegin>inend) {
  5.             return null;
  6.         }
  7.         TreeNode root = new TreeNode(postorder[postIndex]);
  8.         int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
  9.         postIndex--; 
  10.         root.right=buildTreeChild(inorder,rootIndex+1,inend,postorder);
  11.         root.left=buildTreeChild(inorder,inbegin,rootIndex-1,postorder);
  12.         return root;
  13.     }
  14.     public int findIndex(int[] inorder,int inbegin,int inend,int key) {
  15.         for(int i=inbegin;i<=inend;i++) {
  16.             if(inorder[i]==key) {
  17.                 return i;
  18.             }
  19.         }
  20.         return -1;
  21.     }
  22.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  23.         if(inorder==null||postorder==null) {
  24.             return null;
  25.         }
  26.         postIndex = postorder.length-1;
  27.         TreeNode root = buildTreeChild(inorder,0,inorder.length-1,postorder);
  28.         return root;
  29.     }
  30. }

7. 二叉树创建字符串

对应leetcode题

结论：
1.当root不为空的情况下，先append它的值。
2.当左子树为空情况下，右子树不为空时，sb直接append“()”；当右子树为空时，什么都不做。当左子树不为空时，先append"("，再递归它的左子树，左子树递归完后append")" 。
3.当右子树为空，什么都不做，当右子树不为空，则先append"("，再递归它的右子树，右子树递归完后append")" 。

  1. class Solution {
  2.     public void tree2strTree(TreeNode root,StringBuilder sb) {
  3.         if(root==null) {
  4.             return;
  5.         }
  6.         sb.append(root.val);
  7.         if(root.left==null) {
  8.             if(root.right==null) {
  9.                 return;
  10.             }else {
  11.                 sb.append("()");
  12.             }
  13.         }else {
  14.             sb.append("(");
  15.             tree2strTree(root.left,sb);
  16.             sb.append(")");
  17.         }
  18.         if(root.right==null) {
  19.             return;
  20.         }else {
  21.             sb.append("(");
  22.             tree2strTree(root.right,sb);
  23.             sb.append(")");
  24.         }
  25.     }
  26.     public String tree2str(TreeNode root) {
  27.         StringBuilder sb = new StringBuilder();
  28.         if(root==null) {
  29.             return null;
  30.         }
  31.         tree2strTree(root,sb);
  32.         return sb.toString();
  33.     }
  34. }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/ZJRUIII/article/details/122350504

内容来源于网络，如有侵权，请联系作者删除！

Java数据结构算法

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多

    目录

    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com