`

Binary Tree的题目总结(二)

阅读更多
这篇文章列出了leetcode中有关二叉树遍历的题目,之前在二叉树的深搜和广搜中介绍过,这里再重复一下,因为这都是最基本的操作,需要我们熟练掌握。

1,Binary Tree Level Order Traversal
二叉树的广度优先搜索,输出所有节点的值,说的广搜,我们一律用队列来完成,代码如下:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        int count = 0;
        int helper = 1;
        if(root == null) return llist;
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(helper > 0){
                list.add(node.val);
                helper --;
            }
            if(node.left != null) {
                queue.offer(node.left);
                count ++;
            }
            if(node.right != null) {
                queue.offer(node.right);
                count ++;
            }
            
            if(helper == 0) {
                llist.add(new ArrayList<Integer>(list));
                list.clear();
                helper = count;
                count = 0;
            }
        }
        return llist;
    }
}


2,Binary Tree Level Order Traversal II
给定二叉树:{3,9,20,#,#,15,7},
输出:[[15,7], [9,20], [3]]

这是第一题的变形,仅仅把结果逆序输出,我们用链表中的addFirst()方法就解决了。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> llist = new LinkedList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if(root == null) return llist;
        queue.offer(root);
        int count = 0;
        int helper = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(helper > 0) {
                list.add(node.val);
                helper --;
            }
            if(node.left != null) {
                queue.offer(node.left);
                count ++;
            }
            if(node.right != null) {
                queue.offer(node.right);
                count ++;
            }
            
            if(helper == 0) {
                llist.addFirst(new ArrayList<Integer>(list));
                list.clear();
                helper = count;
                count = 0;
            }
        }
        return llist;
    }
}


下面是二叉树的前序遍历,中序遍历,后序遍历,都属于深搜,我们用堆栈来完成。

3,Binary Tree Inorder Traversal
二叉树的中序遍历,输出所有节点的值。

代码如下:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root == null) return list;
        while(root != null || !stack.isEmpty()) {
            if(root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode node = stack.pop();
                list.add(node.val);
                root = node.right;
            }
        }
        return list;
    }
}


4,Binary Tree Preorder Traversal
二叉树的前序遍历,输出所有节点的值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root == null) return list;
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            list.add(tem.val);
            if(tem.right != null) {
                stack.push(tem.right);
            }
            if(tem.left != null) {
                stack.push(tem.left);
            }
        }
        return list;
    }
}


5,Binary Tree Postorder Traversal
二叉树的后序遍历,输出所有节点的值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root == null) return list;
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.addFirst(node.val);
            if(node.left != null) {
                stack.push(node.left);
            }
            if(node.right != null) {
                stack.push(node.right);
            }
        }
        return list;
    }
}
分享到:
评论

相关推荐

    binarytree.rar

    二叉树是一种在计算机科学中广泛使用的数据结构,它的每个节点最多有两个子节点,通常称为左子节点和右...解压“binarytree.rar”,查看其中的文件,理解数据结构,并根据给定的描述编写代码,以实现二叉树的前序遍历。

    leetcode的题目:Balanced Binary Tree

    在LeetCode的"Balanced Binary Tree"题目中,通常要求判断给定的二叉树是否是平衡的。这个问题可以通过递归或迭代的方式来解决。递归方法是分别检查左子树和右子树是否平衡,以及它们的高度。迭代方法则可以使用层次...

    java-leetcode题解之Binary Tree Cameras.java

    题目“Binary Tree Cameras”是一个有关二叉树的算法问题,要求编写一个函数来计算在二叉树的所有节点上放置监控摄像头的最小数量,以便监控到树的所有节点。这个问题是一个经典的动态规划问题,需要考虑如何最小化...

    java-leetcode题解之Maximum Binary Tree II.java

    本篇内容将深入探讨一个特定的LeetCode题目:“Maximum Binary Tree II”(最大二叉树 II),并提供Java语言的解决方案。 最大二叉树是数据结构中树的一种特殊形态,它被用来表示一系列数中的最大值。构建最大...

    java-leetcode题解之Distribute Coins in Binary Tree.java

    知识点的总结强调了递归在处理树形结构问题中的重要性,并指出了在解决“Distribute Coins in Binary Tree”这类问题时需要注意的关键点,如递归函数的设计、递归过程中信息的传递与更新,以及如何高效地统计并返回...

    C++-leetcode题解之655. Print Binary Tree.cpp

    题目编号655的“Print Binary Tree”(打印二叉树),是一道涉及到二叉树结构遍历和层序遍历打印的题目。解决这个问题需要了解二叉树的基本概念,包括节点、根节点、子节点、左子树、右子树等,同时还需要掌握层序...

    java-leetcode题解之Find Elements in a Contaminated Binary Tree.java

    在解决“Find Elements in a Contaminated Binary Tree”这类LeetCode题目时,首先要了解的是二叉树的数据结构和基本操作。二叉树是每个节点最多有两个子节点的树结构,分为左子节点和右子节点。而所谓的“污染的...

    Binary Tree-二叉树

    "二叉树oj"可能是针对在线评测系统的二叉树题目解决方案。"topk问题"指向了一个与二叉堆密切相关的算法问题,即如何高效地找到一组数据中的前k个最大或最小元素。"二叉堆"文件名直接表明了该文件与二叉堆的实现和...

    java-leetcode题解之Maximum Binary Tree.java

    本篇文章将详细解读Java语言解决LeetCode上的一个特定算法题——“Maximum Binary Tree”(最大二叉树)的解题过程。最大二叉树是指从给定的无序整数数组中构建出的一个二叉树,其中根节点的值是数组中最大的元素,...

    python-leetcode题解之226-Invert-Binary-Tree.py

    LeetCode作为一个在线编程平台,为编程爱好者提供了大量算法和数据结构的练习题目,Invert Binary Tree便是其中的一个题目。这个题目的目标是实现一个函数,这个函数的目的是将输入的二叉树进行“翻转”,即将二叉树...

    java-leetcode题解之Average of Levels in Binary Tree.java

    在Java编程语言中,解决“Average of Levels in Binary Tree”(二叉树每一层的平均值)这个问题是二叉树遍历和处理的一个典型应用。这个问题通常在LeetCode这样的在线编程平台上出现,要求编写者能够理解二叉树的...

    java-leetcode题解之Construct Binary Tree from String.java

    而构建二叉树(Binary Tree)是算法面试中经常出现的题目,LeetCode作为一款广泛使用的编程练习平台,提供了大量这类题目,帮助开发者提升技能。本文将详细介绍如何用Java语言解决LeetCode上的特定题目——从字符串...

    java-leetcode题解之All Nodes Distance K in Binary Tree.java

    All Nodes Distance K in Binary Tree不仅考察了对二叉树的深入理解,还考察了将树转换为图,并利用图搜索算法解决问题的能力。这要求解题者具备扎实的数据结构基础和算法知识,以及将理论知识灵活应用到实际编程...

    recover-the-binary-tree.zip_The Tree

    题目中的"recover-the-binary-tree.zip_The Tree"文件包含了一个名为"recover the binary tree.cpp"的源代码文件,这很可能是实现这个恢复过程的C++程序。为了理解并执行这个过程,我们需要了解以下步骤: 1. **...

    c语言-leetcode题解之0094-binary-tree-inorder-traversal.zip

    其中,二叉树的中序遍历(binary tree inorder traversal)是数据结构中的一个经典算法问题。中序遍历的特点是先访问左子树,然后是根节点,最后是右子树,这种遍历方式适用于二叉搜索树,能够得到排序的序列。 在...

    java-leetcode题解之Construct String from Binary Tree.java

    在讲解Java解决LeetCode题库中“根据二叉树构造字符串”问题的题解时,我们首先要了解这个题目的具体要求。这个题目要求我们利用给定的二叉树来构造一个字符串。每个节点应该被表示为括号以及其对应的值。左子节点和...

    C++-leetcode题解之654. Maximum Binary Tree.cpp

    在LeetCode题库中,编号为654的最大二叉树问题,是数据结构专题中的一道经典题目。本题要求根据给定的无序整数数组,构造出一个二叉树,并使得该二叉树的大小(节点总数)最大。 本题解涉及的关键知识点包括: 1. ...

    MengZhaoFly#sword-byteDance-fe#二叉树的所有路径(binary-tree-paths)1

    题目二叉树所有路径题解* Definition for a binary tree node.* function TreeNode(val) {* @para

    java-leetcode题解之Closest Leaf in a Binary Tree.java

    首先,要解决这个问题,我们需要理解题目要求。问题通常描述为:给定一棵二叉树,找到与指定节点距离最近的叶子节点。这就意味着我们需要从目标节点出发,在树中搜索最短路径,直到到达一个没有子节点的节点,即叶子...

    python-leetcode题解之104-Maximum-Depth-of-Binary-Tree

    《LeetCode题解之104-Maximum Depth of Binary Tree》是一篇针对编程题目的详细解释与Python代码示例的文章。题目要求编写一个函数来找出二叉树的最大深度。在计算机科学中,二叉树的深度是指从根节点到最远叶子节点...

Global site tag (gtag.js) - Google Analytics