devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java-数据结构-二叉树＜一＞_java中inverttree函数的用法

作者：IT小白 | 2024-06-22 22:37:26

赞

踩

java中inverttree函数的用法

一. 二叉树的简单介绍

        二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。

        其中，满二叉树和完全二叉树是其中比较特殊的类型。如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树，完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，即缺失的叶子节点只能在最后一层的叶子节点上。

二. 二叉树的典型代码实现

  1.   public class TreeNode {
  2.       int val;
  3.       TreeNode left;
  4.       TreeNode right;
  5.       TreeNode() {}
  6.       TreeNode(int val) { this.val = val; }
  7.       TreeNode(int val, TreeNode left, TreeNode right) {
  8.           this.val = val;
  9.           this.left = left;
  10.           this.right = right;
  11.       }
  12.  }

三. 二叉树的遍历

        二叉树的遍历一般有三种方式，递归方式，使用栈和Morris 遍历。递归的方式实现较为简单，栈则是显示维护一个空间，Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。

前序遍历

递归

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

栈 

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

 Morris 遍历

  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<Integer>();
  4.         if (root == null) {
  5.             return res;
  6.         }
  7.  
  8.         TreeNode p1 = root, p2 = null;
  9.  
  10.         while (p1 != null) {
  11.             p2 = p1.left;
  12.             if (p2 != null) {
  13.                 while (p2.right != null && p2.right != p1) {
  14.                     p2 = p2.right;
  15.                 }
  16.                 if (p2.right == null) {
  17.                     res.add(p1.val);
  18.                     p2.right = p1;
  19.                     p1 = p1.left;
  20.                     continue;
  21.                 } else {
  22.                     p2.right = null;
  23.                 }
  24.             } else {
  25.                 res.add(p1.val);
  26.             }
  27.             p1 = p1.right;
  28.         }
  29.         return res;
  30.     }
  31. }

中序遍历

递归

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

栈/迭代

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<Integer>();
  4.         Deque<TreeNode> stk = new LinkedList<TreeNode>();
  5.         while (root != null || !stk.isEmpty()) {
  6.             while (root != null) {
  7.                 stk.push(root);
  8.                 root = root.left;
  9.             }
  10.             root = stk.pop();
  11.             res.add(root.val);
  12.             root = root.right;
  13.         }
  14.         return res;
  15.     }
  16. }

 Morris

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<Integer>();
  4.         TreeNode predecessor = null;
  5.  
  6.         while (root != null) {
  7.             if (root.left != null) {
  8.                 // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
  9.                 predecessor = root.left;
  10.                 while (predecessor.right != null && predecessor.right != root) {
  11.                     predecessor = predecessor.right;
  12.                 }
  13.                 
  14.                 // 让 predecessor 的右指针指向 root，继续遍历左子树
  15.                 if (predecessor.right == null) {
  16.                     predecessor.right = root;
  17.                     root = root.left;
  18.                 }
  19.                 // 说明左子树已经访问完了，我们需要断开链接
  20.                 else {
  21.                     res.add(root.val);
  22.                     predecessor.right = null;
  23.                     root = root.right;
  24.                 }
  25.             }
  26.             // 如果没有左孩子，则直接访问右孩子
  27.             else {
  28.                 res.add(root.val);
  29.                 root = root.right;
  30.             }
  31.         }
  32.         return res;
  33.     }
  34. }

后序遍历

递归

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

栈/迭代

  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.  
  8.         Deque<TreeNode> stack = new LinkedList<TreeNode>();
  9.         TreeNode prev = null;
  10.         while (root != null || !stack.isEmpty()) {
  11.             while (root != null) {
  12.                 stack.push(root);
  13.                 root = root.left;
  14.             }
  15.             root = stack.pop();
  16.             if (root.right == null || root.right == prev) {
  17.                 res.add(root.val);
  18.                 prev = root;
  19.                 root = null;
  20.             } else {
  21.                 stack.push(root);
  22.                 root = root.right;
  23.             }
  24.         }
  25.         return res;
  26.     }
  27. }

 Morris

  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.  
  8.         TreeNode p1 = root, p2 = null;
  9.  
  10.         while (p1 != null) {
  11.             p2 = p1.left;
  12.             if (p2 != null) {
  13.                 while (p2.right != null && p2.right != p1) {
  14.                     p2 = p2.right;
  15.                 }
  16.                 if (p2.right == null) {
  17.                     p2.right = p1;
  18.                     p1 = p1.left;
  19.                     continue;
  20.                 } else {
  21.                     p2.right = null;
  22.                     addPath(res, p1.left);
  23.                 }
  24.             }
  25.             p1 = p1.right;
  26.         }
  27.         addPath(res, root);
  28.         return res;
  29.     }
  30.  
  31.     public void addPath(List<Integer> res, TreeNode node) {
  32.         int count = 0;
  33.         while (node != null) {
  34.             ++count;
  35.             res.add(node.val);
  36.             node = node.right;
  37.         }
  38.         int left = res.size() - count, right = res.size() - 1;
  39.         while (left < right) {
  40.             int temp = res.get(left);
  41.             res.set(left, res.get(right));
  42.             res.set(right, temp);
  43.             left++;
  44.             right--;
  45.         }
  46.     }
  47. }

四. leetcode实战

1. leetcode226 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

  1. class Solution {
  2. 	public TreeNode invertTree(TreeNode root) {
  3. 		//递归函数的终止条件，节点为空时返回
  4. 		if(root==null) {
  5. 			return null;
  6. 		}
  7. 		//下面三句是将当前节点的左右子树交换
  8. 		TreeNode tmp = root.right;
  9. 		root.right = root.left;
  10. 		root.left = tmp;
  11. 		//递归交换当前节点的 左子树
  12. 		invertTree(root.left);
  13. 		//递归交换当前节点的 右子树
  14. 		invertTree(root.right);
  15. 		//函数返回时就表示当前这个节点，以及它的左右子树
  16. 		//都已经交换完了
  17. 		return root;
  18. 	}
  19. }
  20.

本题小结（1）先在一棵树上操作交换，典型的交换的思想

              （2）然后递归左子树和右子树

2. leetcode104 & leetcode111 二叉树的最大/小深度

        给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

最大深度

  1. class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.         if (root == null) {
  4.             return 0;
  5.         } else {
  6.             int leftHeight = maxDepth(root.left);
  7.             int rightHeight = maxDepth(root.right);
  8.             return Math.max(leftHeight, rightHeight) + 1;
  9.         }
  10.     }
  11. }

最小深度

错误的版本：

  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root == null){
  4.             return 0;
  5.         }else{
  6.             int leftL = minDepth(root.left);
  7.             int rightL = minDepth(root.right);
  8.             return Math.min(leftL,rightL)+1;
  9.         }
  10.     }
  11. }

正确版本：

  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root == null) return 0;
  4.         //这道题递归条件里分为三种情况
  5.         //1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
  6.         if(root.left == null && root.right == null) return 1;
  7.         //2.如果左孩子和由孩子其中一个为空，那么需要返回比较大的那个孩子的深度        
  8.         int m1 = minDepth(root.left);
  9.         int m2 = minDepth(root.right);
  10.         //这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;
  11.         if(root.left == null || root.right == null) return m1 + m2 + 1;
  12.         
  13.         //3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可
  14.         return Math.min(m1,m2) + 1; 
  15.     }
  16. }
  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root == null) return 0;
  4.         int rightdeep = minDepth(root.right);
  5.         int leftdeep = minDepth(root.left);
  6.         if(root.left ==  null || root.right == null) return rightdeep+leftdeep+1;
  7.         return Math.min(rightdeep,leftdeep)+1;
  8.     }
  9. }
  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if (root == null) return 0;
  4.         else if (root.left == null) return minDepth(root.right) + 1;
  5.         else if (root.right == null) return minDepth(root.left) + 1;
  6.         else return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
  7.     }
  8. }

 本题小结：（1）这题和求最大值不一样，最大的区别在于若左右节点有一个为空怎么办

参考来源：

【1】leetcode 官方解题 二叉树的前序遍历

【2】leetcode wang_ni_ma 动画演示 两种实现 226. 翻转二叉树 

【3】leetcode 房建斌学算法 二叉树的最小深度-理解递归结束条件

【4】百度百科 二叉树  

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/747857
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号