通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode探索之二叉树学习 树的遍历

533人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode  | 

作者:因情语写

链接:https://www.qingyu.blue/article/614

声明:请尊重原作者的劳动,如需转载请注明出处


    在上节的介绍中,相信大家已经熟知了树和二叉树的基本概念。

    本章节,我们把重点放在介绍二叉树中几种常见的遍历方法。掌握这几种遍历方法,会加深你对树这个数据结构的理解,并为以后的学习打下扎实的基础。

    本章目标:

  1. 理解和区分树的遍历方法
  2. 能够运用递归方法解决树的为前序遍历中序遍历后序遍历问题
  3. 能用运用迭代方法解决树的为前序遍历、中序遍历和后序遍历问题
  4. 能用运用广度优先搜索解决树的层序遍历问题

 树的遍历 - 介绍

    前序遍历

    前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。

    请看下面的例子:

    中序遍历

    中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。

    让我们一起来看树的中序遍历:

    通常来说,对于二叉搜索树,我们可以通过中序遍历得到一个递增的有序序列。 我们将在另一张卡片(数据结构介绍 – 二叉搜索树)中再次提及。

    后序遍历

    后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点。

    我们一起来看后序遍历的动画演示:

    值得注意的是,当你删除树中的节点时,删除过程将按照后序遍历的顺序进行。 也就是说,当你删除一个节点时,你将首先删除它的左节点和它的右边的节点,然后再删除节点本身。

    另外,后序在数学表达中被广泛使用。 编写程序来解析后缀表示法更为容易。 这里是一个例子:

    您可以使用中序遍历轻松找出原始表达式。 但是程序处理这个表达式时并不容易,因为你必须检查操作的优先级。

    如果你想对这棵树进行后序遍历,使用栈来处理表达式会变得更加容易。 每遇到一个操作符,就可以从栈中弹出栈顶的两个元素,计算并将结果返回到栈中。

    递归和迭代

    请练习文章后面习题中的三种遍历方法。 您可以通过递归或迭代方法实现算法,并比较它们之间的差异。

    算法-二叉树的前序遍历

给定一个二叉树,返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        result.clear();
        preorder(root);
        return result;
    }
    
    private void preorder(TreeNode node) {
        if(null != node){
            result.add(node.val);
            preorder(node.left);
            preorder(node.right);
        }
    }
}

    上面是递归的方法,下面看一下非递归的

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pollLast();
      output.add(node.val);
      if (node.right != null) {
        stack.add(node.right);
      }
      if (node.left != null) {
        stack.add(node.left);
      }
    }
    return output;
  }
}

    非递归栈,先进右子树,再进左子树,这样出时先出左子树,再出右子树

    算法-中序遍历二叉树

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
}
    
public void inorder(TreeNode node, List<Integer> result){
    if(node != null){
        inorder(node.left, result);
        result.add(node.val);
        inorder(node.right, result);
   }
}

     上面是递归的方法,再看一下非递归的方法

// 用栈,非递归
    // 处理树:对一个节点,如果有左孩子且没被处理过,入栈,然后处理最左没被处理的那个节点,如果此节点有右孩子,右孩子入栈
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();
        List<TreeNode> visited = new ArrayList<>();
        TreeNode temp, left;
        
        if(root == null){
            return result;
        }
        
        stack.push(root);

        while(!stack.isEmpty()){
            temp = stack.peek();
            while(temp.left != null && !visited.contains(temp.left)){
                stack.push(temp.left);
                temp = temp.left;
            }

            result.add(temp.val);
            visited.add(temp);
            stack.pop();

            if(null != temp.right){
                stack.push(temp.right);
            }
        }
        
        return result;
    }

    处理结点的顺序:对一个节点,如果有左孩子且没被处理过,入栈,然后处理最左没被处理的那个节点,如果此节点有右孩子,右孩子入栈

    算法-二叉树的后序遍历

给定一个二叉树,返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }
    
    private void postorder(TreeNode node, List<Integer> result) {
        if(node != null){
            postorder(node.left, result);
            postorder(node.right, result);
            result.add(node.val);
        }
    }
}

    上面是递归的方法,下面再看一下非递归的方法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }
    
    private void postorder(TreeNode node, List<Integer> result) {
        if(node != null){
            postorder(node.left, result);
            postorder(node.right, result);
            result.add(node.val);
        }
    }
    
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        List<TreeNode> visited = new ArrayList<>();

        if (root == null) {
          return result;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
              TreeNode node = stack.peek();

              while (node.left != null && !visited.contains(node.left)) {
                  stack.push(node.left);
                  node = node.left;
              }
            
            if(node.right != null && !visited.contains(node.right)){
                stack.push(node.right);
            }else{
                stack.pop();
                result.add(node.val);
                visited.add(node);
                
            }
        }
        return result;
    }
}

    和先序遍历的非递归方法类似,要用到标记

    层序遍历 - 介绍

    层序遍历就是逐层遍历树结构。

    广度优先搜索是一种广泛运用在树或图这类数据结构中,遍历或搜索的算法。 该算法从一个根节点开始,首先访问节点本身。 然后遍历它的相邻节点,其次遍历它的二级邻节点、三级邻节点,以此类推。

    当我们在树中进行广度优先搜索时,我们访问的节点的顺序是按照层序遍历顺序的。

    这是一个层序顺序遍历的例子:

    通常,我们使用一个叫做队列的数据结构来帮助我们做广度优先搜索。 如果您对队列不熟悉,可以在我们即将推出的另一张卡片中找到更多有关信息。


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!