Binary Tree Traversal

浠ラ箍发布于2019-08-14 17:17 / 1974人阅读

PostOrder

public class Solution {
    // Important, when you pop a node, ensure its children are traversed.
    public List postorderTraversal(TreeNode root) {
        ArrayDeque s = new ArrayDeque();
        List ans = new ArrayList();
        TreeNode cur = root;
        
        while (cur != null || !s.isEmpty()) {
            while (cur != null) {
                s.push(cur);
                cur = cur.left;
            }
            
            while (!s.isEmpty() && cur == s.peek().right) {
                cur = s.pop();
                ans.add(cur.val);
            }
            
            if (s.isEmpty()) cur = null; else cur = s.peek().right;
        }
        
        return ans;
    }
    
}

PreOrder

public class Solution {
    public List preorderTraversal(TreeNode root) {
        List res = new LinkedList();
        ArrayDeque stk = new ArrayDeque();
        TreeNode cur = root;
        
        while(cur != null || !stk.isEmpty()){
            if(cur != null) {
                stk.push(cur);
                res.add(cur.val);   // add val before going to children
                cur = cur.left;
            } else {
                TreeNode node = stk.pop();
                cur = node.right;
            }
        }
        return res;
    }
}

InOrder

public class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        if(root == null) return res;
        ArrayDeque stk = new ArrayDeque();
        TreeNode cur = root;
        
        while(cur != null || !stk.isEmpty()){
            if(cur !=null) {
                stk.push(cur);
                cur = cur.left; 
            } else {
                TreeNode node = stk.pop();
                res.add(node.val);        // add after all left children
                node = node.right;
            }
        }
        return res;
    }
}

PreOrder

public class Solution {
    public List preorderTraversal(TreeNode root) {
        List res = new LinkedList();
        ArrayDeque stk = new ArrayDeque();
        if(root == null) return res;
        TreeNode cur = root;
        stk.push(cur);
        
        while(!stk.isEmpty()){
            cur = stk.pop();
            res.add(cur.val);
            if(cur.right != null) stk.push(cur.right);
            if(cur.left != null) stk.push(cur.left);
        }
        return res;
    }
}

InOrder

public class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        if(root == null) return res;
        ArrayDeque stk = new ArrayDeque();
        TreeNode cur = root;
        
        while(cur != null || !stk.isEmpty()){
            while(cur != null) {
                stk.push(cur);
                cur = cur.left;
            }
            cur = stk.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

云服务器 GPU云服务器 binary-tree binary-search-tree Traversal Binary

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

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

[Leetcode] Binary Tree Traversal 二叉树遍历

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

RaoMeng 2019-08-14 12:25 评论0 收藏0
[Leetcode-Tree]Binary Tree Level Order Traversal

摘要：解题思路层次遍历二叉树，我们采用队列，本题的注意点是需要分割出每一层的序列，所以在从队列中取元素之前，我们要先记录队列的大小，以表示这一层中节点的个数。 Binary Tree Level Order TraversalGiven a binary tree, return the level order traversal of its nodes values. (ie, from...

Half 2019-08-16 10:26 评论0 收藏0
[Leetcode] Construct Binary Tree from Traversal 根据

摘要：二分法复杂度时间空间思路我们先考察先序遍历序列和中序遍历序列的特点。对于中序遍历序列，根在中间部分，从根的地方分割，前半部分是根的左子树，后半部分是根的右子树。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...

caoym 2019-08-14 12:32 评论0 收藏0
leetcode102. Binary Tree Level Order Traversal

摘要：题目要求对于一棵树进行序遍历。水平遍历即遍历结束当前行以后再遍历下一行，并将每行的结果按行填入到数组中返回。利用水平遍历的话，我们只需要知道当前元素在树中的高度就可以知道应当插入到那个数组中。题目要求 Given a binary tree, return the level order traversal of its nodes values. (ie, from left to...

Coding01 2019-08-16 12:09 评论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] 429. N-ary Tree Level Order Traversal (

429. N-ary Tree Level Order Traversal Given an n-ary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example, given a 3-ary tree:showImg(https...

LiangJ 2019-08-19 11:18 评论0 收藏0