二叉树的遍历

1.二叉树的遍历

二叉树主要有两种遍历方式:

深度优先遍历:先往深走,遇到叶子节点再往回走。

  • 前序遍历(递归法,迭代法) 中左右
  • 中序遍历(递归法,迭代法) 左中右
  • 后序遍历(递归法,迭代法) 左右中

广度优先遍历:一层一层的去遍历。

  • 层次遍历(迭代法)

     二叉树的遍历

 

 

 对比图可以理解一下遍历的过程,前中后序遍历涉及递归和迭代两种方法讲解。

2.LeetCode链接

前序遍历:https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/

中序遍历:https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/

后序遍历:https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/

层序遍历:https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/

感兴趣的可以去练练手!!!

3.前序遍历

前序遍历的顺序是中左右,即先根节点、左子树、右子树,那么我们先考虑递归进行求解。

要打印出前序遍历节点的数值,所以参数里需要放节点的数值,除了这一点就不需要在处理什么数据了也不需要有返回值,所以递归函数返回类型就是void

   Traversal(TreeNode root, List<Integer> list) 

当前遍历的节点是空了,那么本层递归就要要结束了,所以如果当前遍历的这个节点是空,就直接return

 if (cur == NULL) return; 

前序遍历是中左右的循序,所以在单层递归的逻辑,是要先取中节点的数值

list.add(root.val);

Traversal(root.left, list);

Traversal(root.right, list); 

所以总体的递归代码如下:

class Solution {     public List<Integer> preorderTraversal(TreeNode root) {         List<Integer> result = new ArrayList<Integer>();         preorder(root, result);         return result;     }      public void preorder(TreeNode root, List<Integer> result) {         if (root == null) {             return;         }         result.add(root.val);         preorder(root.left, result);         preorder(root.right, result);     } }

对于迭代法,难度会更大一点!!!

前序遍历是中左右,每次先处理的是中间节点,那么先将根节点放入栈中,然后将右孩子加入栈,再加入左孩子。为什么要先加入 右孩子,再加入左孩子呢? 因为这样出栈的时候才是中左右的顺序

所以我们不难写出代码如下:

class Solution {     public List<Integer> preorderTraversal(TreeNode root) {         List<Integer> result = new ArrayList<>();         if (root == null){             return result;         }         Stack<TreeNode> stack = new Stack<>();         stack.push(root);         while (!stack.isEmpty()){             TreeNode node = stack.pop();             result.add(node.val);             if (node.right != null){                 stack.push(node.right);             }             if (node.left != null){                 stack.push(node.left);             }         }         return result;     } }

4.中序遍历

中序遍历的顺序是左中右,即先左子树、根节点、右子树,那么我们先考虑递归进行求解。

  思路和上面一样,唯一的区别就是变了顺序,所以总体的递归代码如下:

class Solution {     public List<Integer> preorderTraversal(TreeNode root) {         List<Integer> result = new ArrayList<Integer>();         preorder(root, result);         return result;     }      public void preorder(TreeNode root, List<Integer> result) {         if (root == null) {             return;         }         preorder(root.left, result);         result.add(root.val);   //注意         preorder(root.right, result);     } }

  对于迭代法,难度会更大一点!!!

  中序遍历是左中右,但是代码和上面有一些不同,中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部再开始处理节点(也就是在把节点的数值放进result数组中),这就造成了处理顺序和访问顺序是不一致的。在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。

  所以我们可以写出代码如下:

class Solution {     public List<Integer> inorderTraversal(TreeNode root) {         List<Integer> result = new ArrayList<>();         if (root == null){             return result;         }         Stack<TreeNode> stack = new Stack<>();         TreeNode cur = root;         while (cur != null || !stack.isEmpty()){            if (cur != null){                stack.push(cur);                cur = cur.left;            }else{                cur = stack.pop();                result.add(cur.val);                cur = cur.right;            }         }         return result;     } }

5.后序遍历

  后序遍历的顺序是左右中,即先左子树、右子树、根节点,那么我们先考虑递归进行求解。

  思路和上面一样,唯一的区别就是变了顺序,所以总体的递归代码如下:

class Solution {     public List<Integer> preorderTraversal(TreeNode root) {         List<Integer> result = new ArrayList<Integer>();         preorder(root, result);         return result;     }      public void preorder(TreeNode root, List<Integer> result) {         if (root == null) {             return;         }         preorder(root.left, result);         preorder(root.right, result);         result.add(root.val);   //注意     } }

  对于迭代法,会前序遍历难度会小一点!!!

  先序遍历是中左右,后续遍历是左右中,那么我们只需要调整一下先序遍历的代码顺序,就变成中右左的遍历顺序,然后在反转result数组,输出的结果顺序就是左右中了,如下图:

    二叉树的遍历

  所以我们可以很快的写出代码如下:

class Solution {     public List<Integer> postorderTraversal(TreeNode root) {         List<Integer> result = new ArrayList<>();         if (root == null){             return result;         }         Stack<TreeNode> stack = new Stack<>();         stack.push(root);         while (!stack.isEmpty()){             TreeNode node = stack.pop();             result.add(node.val);             if (node.left != null){                 stack.push(node.left);             }             if (node.right != null){                 stack.push(node.right);             }         }         Collections.reverse(result);         return result;     } }

  注意,这里主要是入栈顺序变了,变成先左后右!!!

6.层序遍历

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

了解了思路,我们可以很快的写出层序遍历的代码:

class Solution {     public List<List<Integer>> resList = new ArrayList<List<Integer>>();     public List<List<Integer>> levelOrder(TreeNode root) {         checkFun02(root);         return resList;     }     public void checkFun02(TreeNode node) {         if (node == null) return;         Queue<TreeNode> que = new LinkedList<TreeNode>();         que.offer(node);         while (!que.isEmpty()) {             List<Integer> itemList = new ArrayList<Integer>();             int len = que.size();             while (len > 0) {                 TreeNode tmpNode = que.poll();                 itemList.add(tmpNode.val);                 if (tmpNode.left != null) que.offer(tmpNode.left);                 if (tmpNode.right != null) que.offer(tmpNode.right);                 len--;             }             resList.add(itemList);         }     } }

  主要就是建立一个队列,依次对出队列的数的左右子树入队,同时记录下当前队列的大小,这样可以每一次得到一层的数

  怎么样,看完以后是不是简单多了,当然得有一点点这个方面基础,不然看起来还是有点费劲!!!

 

发表评论

相关文章