美文网首页
二叉树的三种遍历

二叉树的三种遍历

作者: marsrocking | 来源:发表于2020-04-18 14:07 被阅读0次

    概念:

    树 是一种经常用到的数据结构,用来模拟具有树状结构性质的数据集合。
    
    树里的每一个节点有一个根植和一个包含所有子节点的列表。从图的观点来看,树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。
    
    二叉树是一种更为典型的树树状结构。如它名字所描述的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。
    

    有两种遍历树的策略:

    1.深度优先搜索(DFS)

    在这个策略中,我们采用深度作为优先级,以便从跟开始一直到达某个确定的叶子,然后再返回根到达另一个分支。
    
    深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为前序遍历,中序遍历和后序遍历。
    

    2.宽度优先搜索(BFS)

      我们按照高度顺序一层一层的访问整棵树,高层次的节点将会比低层次的节点先被访问到。
    
    image.png

    前序遍历-使用宽度优先搜索

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

    示例:


    image.png

    方法 1:迭代
    首先,定义树的存储结构TreeNode

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
    
      TreeNode(int x) {
        val = x;
      }
    }
    
    

    从根节点开始,每次迭代弹出当前栈顶元素,并将其孩子节点压入栈中,先压右孩子再压左孩子。

    在这个算法中,输出到最终结果的顺序按照 Top->Bottom 和 Left->Right,符合前序遍历的顺序。

    public:
        vector<int> 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;
      }
     }
    
    

    算法复杂度
    时间复杂度:访问每个节点恰好一次,时间复杂度为O(N) ,其中 N 是节点的个数,也就是树的大小。
    空间复杂度:取决于树的结构,最坏情况存储整棵树,因此空间复杂度是 O(N)。

    方法二:递归

    class Solution {
        List<Integer> lists;
    
        public Solution(){
             lists=new ArrayList<>();
        }
        
        public List<Integer> preorderTraversal(TreeNode root) {
             //根左右
             if(root==null) return lists;
             lists.add(root.val);
             preorderTraversal(root.left);
             preorderTraversal(root.right);
             return lists;
        }
    }
    

    方法 3:莫里斯遍历
    方法基于 莫里斯的文章,可以优化空间复杂度。算法不会使用额外空间,只需要保存最终的输出结果。如果实时输出结果,那么空间复杂度是 O(1)。

    算法的思路是从当前节点向下访问先序遍历的前驱节点,每个前驱节点都恰好被访问两次。

    首先从当前节点开始,向左孩子走一步然后沿着右孩子一直向下访问,直到到达一个叶子节点(当前节点的中序遍历前驱节点),所以我们更新输出并建立一条伪边 predecessor.right = root 更新这个前驱的下一个点。如果我们第二次访问到前驱节点,由于已经指向了当前节点,我们移除伪边并移动到下一个顶点。

    如果第一步向左的移动不存在,就直接更新输出并向右移动。

    class Solution {
      public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<Integer> output = new LinkedList<>();
    
        TreeNode node = root;
        while (node != null) {
          if (node.left == null) {
            output.add(node.val);
            node = node.right;
          }
          else {
            TreeNode predecessor = node.left;
            while ((predecessor.right != null) && (predecessor.right != node)) {
              predecessor = predecessor.right;
            }
    
            if (predecessor.right == null) {
              output.add(node.val);
              predecessor.right = node;
              node = node.left;
            }
            else{
              predecessor.right = null;
              node = node.right;
            }
          }
        }
        return output;
      }
    }
    

    算法复杂度
    时间复杂度:每个前驱恰好访问两次,因此复杂度是 O(N),其中 N 是顶点的个数,也就是树的大小。
    空间复杂度:我们在计算中不需要额外空间,但是输出需要包含 N 个元素,因此空间复杂度为O(N)。

    代码:LeetCode
    链接:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-bian-li-by-leetcode/
    来源:力扣(LeetCode)

    相关文章

      网友评论

          本文标题:二叉树的三种遍历

          本文链接:https://www.haomeiwen.com/subject/yxvvvhtx.html