[Leetcode] Binary Tree Traversal 二叉树遍历

RaoMeng 发布于2019-08-14 12:25 / 3290人阅读

摘要：栈迭代复杂度时间空间递归栈空间对于二叉树思路用迭代法做深度优先搜索的技巧就是使用一个显式声明的存储遍历到节点，替代递归中的进程栈，实际上空间复杂度还是一样的。对于先序遍历，我们出栈顶节点，记录它的值，然后将它的左右子节点入栈，以此类推。

Binary Tree Preorder Traversal

</>复制代码 
Given a binary tree, return the preorder traversal of its nodes" values.
For example: Given binary tree {1,#,2,3},
</>复制代码 
   1
    
     2
    /
   3
return [1,2,3].

栈迭代 复杂度

时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间对于二叉树b=2

思路

用迭代法做深度优先搜索的技巧就是使用一个显式声明的Stack存储遍历到节点，替代递归中的进程栈，实际上空间复杂度还是一样的。对于先序遍历，我们pop出栈顶节点，记录它的值，然后将它的左右子节点push入栈，以此类推。

代码

</>复制代码 
public class Solution {
    public List preorderTraversal(TreeNode root) {
        Stack s = new Stack();
        List res = new LinkedList();
        if(root!=null) s.push(root);
        while(!s.isEmpty()){
            TreeNode curr = s.pop();
            res.add(curr.val);
            if(curr.right!=null) s.push(curr.right);
            if(curr.left!=null) s.push(curr.left);
        }
        return res;
    }
}

Binary Tree Inorder Traversal

</>复制代码 
Given a binary tree, return the inorder traversal of its nodes" values.
For example: Given binary tree {1,#,2,3},
</>复制代码 
   1
    
     2
    /
   3
return [1,3,2].

栈迭代 复杂度

时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间对于二叉树b=2

思路

用栈中序遍历没有先序遍历那么直观，因为我们不能马上pop出当前元素，而要先把它的左子树都遍历完才能pop它自己。所有我们先将将最左边的所有节点都push进栈，然后再依次pop并记录值，每pop一个元素后再看它有没有右子树，如果右的话，我们再将它的右节点和右子树中最左边的节点都push进栈，再依次pop。

代码

</>复制代码 
public class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new LinkedList();
        Stack s = new Stack();
        //先将最左边的节点都push进栈
        if(root!=null){
            pushAllTheLeft(s, root);
        }
        while(!s.isEmpty()){
            TreeNode curr = s.pop();
            res.add(curr.val);
            //如果有右子树，将右节点和右子树的最左边的节点都push进栈
            if(curr.right != null){
                pushAllTheLeft(s, curr.right);
            }
        }
        return res;
    }
    
    private void pushAllTheLeft(Stack s, TreeNode root){
        s.push(root);
        while(root.left!=null){
            root = root.left;
            s.push(root);
        }
    }
}

Binary Tree Postorder Traversal

</>复制代码 
Given a binary tree, return the postorder traversal of its nodes" values.
For example: Given binary tree {1,#,2,3},
</>复制代码 
   1
    
     2
    /
   3
return [3,2,1].

栈迭代 复杂度

时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间对于二叉树b=2

思路

后序遍历就不能简单的改变pop顺序来实现了，我们知道根节点（这里的根节点不是整个树的根，而是相对于左右节点的跟）是在左右节点都计算完才计算的，所以我们会遇到两次根节点，第一次遇到根节点时我们将左右节点加入栈，但不把根节点pop出去，等到处理完左右节点后，我们又会遇到一次根节点，这时再计算根节点并把它pop出去。为了判断是第一次还是第二次遇到这个根节点，我们可以用一个数据结构把这个信息封装进去，第一次遇到的时候将其设为已经访问了一次，这样第二次遇到时发现已经访问了一次，就可以直接pop了。

代码

</>复制代码 
public class Solution {
    public List postorderTraversal(TreeNode root) {
        Stack s = new Stack();
        List res = new LinkedList();
        if(root!=null) s.push(new PowerNode(root, false));
        while(!s.isEmpty()){
            PowerNode curr = s.peek();
            //如果是第二次访问，就计算并pop该节点
            if(curr.visited){
                res.add(curr.node.val);
                s.pop();
            } else {
            //如果是第一次访问，就将它的左右节点加入stack，并设置其已经访问了一次
                if(curr.node.right!=null) s.push(new PowerNode(curr.node.right, false));
                if(curr.node.left!=null) s.push(new PowerNode(curr.node.left, false));
                curr.visited = true;
            }
        }
        return res;
    }
    
    private class PowerNode {
        TreeNode node;
        boolean visited;
        public PowerNode(TreeNode n, boolean v){
            this.node = n;
            this.visited = v;
        }
    }
}

反向法 复杂度

时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间对于二叉树b=2

思路

还有一种更巧妙的方法，因为后序遍历的顺序是left - right - root，虽然我们不方便直接得到这个顺序，但是它的逆序还是很好得到的，我们可以用root - right - left的顺序遍历树，然后反向添加结果就行了。

代码

</>复制代码 
public class Solution {
    public List postorderTraversal(TreeNode root) {
        Stack stk = new Stack();
        if(root != null) stk.push(root);
        LinkedList res = new LinkedList();
        while(!stk.isEmpty()){
            TreeNode curr = stk.pop();
            // 先添加左后添加右，就是先访问右后访问左
            if(curr.left != null) stk.push(curr.left);
            if(curr.right != null) stk.push(curr.right);
            // 反向添加结果，每次加到最前面
            res.offerFirst(curr.val);
        }
        return res;
    }
}

Binary Tree Level Order Traversal I && II

</>复制代码 
Given a binary tree, return the bottom-up level order traversal of its nodes" values. (ie, from left to right, level by level from leaf to root).
For example: Given binary tree {3,9,20,#,#,15,7},
</>复制代码 
    3
   / 
  9  20
    /  
   15   7
return its bottom-up level order traversal as: (II)
</>复制代码 
[
  [15,7],
  [9,20],
  [3]
]
return its level order traversal as: (I)
</>复制代码 
[
  [3],
  [9,20],
  [15,7]
]

队列迭代 复杂度

时间 O(b^(h+1)-1) 空间 O(b^h)

思路

本题实质是广度优先搜索BFS，而用队列可以轻松的以迭代形式实现它。不过不同于BFS的是，层序遍历需要在队列中记住每一层的分割点，而BFS不关心层数只要遍历到指定元素就行了。为了记住这个分割点，我们在进入下一层之前先记下这一层的元素个数N（其实就是当前queue的大小），然后只遍历N个节点（展开下一层节点的同时queue中会新加入很多下下一层的节点）。遍历完N个节点后记录新的层数，再进入下一层。对于II，返回的层是逆序的，我们只要在结果中，每次把下面新一层加到当前这层的前面就行了

代码

</>复制代码 
public class Solution {
    public List> levelOrder(TreeNode root) {
        List> res = new LinkedList>();
        Queue q = new LinkedList();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            List level = new LinkedList();
            //控制当前层的遍历次数
            for(int i =0; i < size; i++){
                TreeNode curr = q.poll();
                level.add(curr.val);
                if(curr.left!=null) q.offer(curr.left);
                if(curr.right!=null) q.offer(curr.right);
            }
            res.add(level);
            //对于II， 我们要逆序加入
            //res.add(0, level)
        }
        return res;
    }
}

Binary Tree Zigzag Level Order Traversal

</>复制代码 
Given a binary tree, return the zigzag level order traversal of its nodes" values. (ie, from left to right, then right to left for the next level and alternate between).
For example: Given binary tree {3,9,20,#,#,15,7},
</>复制代码 
    3
   / 
  9  20
    /  
   15   7
return its zigzag level order traversal as:
</>复制代码 
[
  [3],
  [20,9],
  [15,7]
]

队列迭代 复杂度

时间 O(b^(h+1)-1) 空间 O(b^h)

思路

ZigZag遍历时，奇数层正序记录，偶数层逆序记录。可以通过结果中已有的层数来判断。

代码

</>复制代码 
public class Solution {
    public List> zigzagLevelOrder(TreeNode root) {
        List> res = new LinkedList>();
        Queue q = new LinkedList();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            List level = new LinkedList();
            for(int i =0; i < size; i++){
                TreeNode curr = q.poll();
                //根据结果中已有的层数控制正序还是逆序
                if(res.size() % 2 == 0){
                    level.add(curr.val);
                } else {
                    level.add(0,curr.val);
                }
                if(curr.left!=null) q.offer(curr.left);
                if(curr.right!=null) q.offer(curr.right);
            }
            res.add(level);
        }
        return res;
    }
}

GPU云服务器云服务器二叉树遍历二叉树的遍历 JS二叉树遍历非递归二叉树遍历

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64468.html

LeetCode 之 JavaScript 解答第94题 —— 二叉树的中序遍历

摘要：小鹿题目二叉树中序遍历给定一个二叉树，返回它的中序遍历。通常递归的方法解决二叉树的遍历最方便不过，但是我还是喜欢增加点难度，用一般的迭代循环来实现。 Time：2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿题目：Binary Tree Inorder Traversal（二叉树中序遍历...

Jason 2019-08-23 17:19 评论0 收藏0
leetcode-102-Binary Tree Level Order Traversal

102. 二叉树的层次遍历题目描述给定一个二叉树，返回其按层次遍历的节点值。（即zhucengde，从左到右访问）。例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回其层次遍历结果为： [ [3], [9,20], [15,7] ] class Solution: def le...

widuu 2019-07-31 11:07 评论0 收藏0
leetcode讲解--94. Binary Tree Inorder Traversal

摘要：题目地址嗯，经典的题目，中序遍历二叉树。代码如下中序遍历先序遍历后序遍历是不是简单的不要不要的，递归就是这么美。右孩子后压栈全部释放出来嗯，总的来说用迭代遍历确实烧脑，没什么性能上的特殊需求还是用递归写法吧，对程序员友好哦。 94. Binary Tree Inorder Traversal Given a binary tree, return the inorder travers...

henry14 2019-07-25 11:22 评论0 收藏0
leetcode-145-Binary Tree Postorder Traversal

摘要：栈的意义价值具有时间性，先进后出。比如递归的后序遍历，先序遍历，二叉树的按层次打印。根据需求不同，在中暂时储存的元素单元也不同，元素的先后顺序也不同。应用对顺序有要求的数据。 stack 栈的意义价值：具有时间性，先进后出。所以具有时间关联顺序的元素可以通过这个时间。比如递归的后序遍历，先序遍历，二叉树的按层次打印。根据需求不同，在stack中暂时储存的元素...

Pandaaa 2019-07-30 17:30 评论0 收藏0

发表评论

登陆后可评论

0条评论

RaoMeng

男|高级讲师

我要关注我要私信

TA的文章

tensorflow

阅读 1876·2023-04-26 02:51
手把手教你用echarts和SovitChart开发带渐变色的柱状图

阅读 2922·2021-09-10 10:50
Windows Server 2022 正式版发布(英文版、简体中文版镜像文件下载)

阅读 3177·2021-09-01 10:48
CSS3中的box-sizing

阅读 3719·2019-08-30 15:53
滑动穿透(锁body)终极探索

阅读 1875·2019-08-29 18:40
PWA 时代的移动端图片优化新思路

阅读 444·2019-08-29 16:16
前端每周清单半年盘点之 CSS 篇

阅读 2075·2019-08-29 13:21
恶心的兼容问题：完美解决IE(IE6/IE7/IE8)不兼容HTML5标签的问题

阅读 1851·2019-08-29 11:07

资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

[Leetcode] Binary Tree Traversal 二叉树遍历

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

相关文章

发表评论

0条评论

男|高级讲师

TA的文章

最新活动

`</>复制代码`

`</>复制代码`

`</>复制代码`

`</>复制代码`

`</>复制代码`

`</>复制代码`

`</>复制代码`

`</>复制代码`