java 容器、二叉树操作、107

时间:2022-02-10 17:27:59

二叉树本身固有的递归性质,通常可以用递归算法解决,虽然递归代码简介,但是性能不如非递归算法。

常用的操作是构建二叉树、遍历二叉树(先序、中序、后序、都属于DFS深度优先搜索算法,使用栈来实现),广度优先BFS使用队列来遍历。

参考博客:

链表、二叉树操作深度优先、广度优先的算法

注意:

java 容器、二叉树操作、107

 

这个图里面虚点框代表的是接口,虚线框代表的是抽象类,实线框代表的实现了接口或者继承了抽象类的类,加粗的实线框代表的是常用类:HashMap、HashSet、ArrayList、LinkedList,这张图没有给出Queue的实现,

java 容器、二叉树操作、107

 

可以看到LinkedList是Deque的实现类,所以to sum up,各种栈、队列的接口实现都可以找LinkedList,只是不同的接口都有不同的方法。

 

下面看leetcode的题目:

【107】Binary Tree Level Order Traversal 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:

[
  [15,7],
  [9,20],
  [3]
]

思路:其实是层序遍历二叉树,编程之美上有这个,其实也就是 BFS,如果使用队列来实现的话,会超时,编程之美上用的vector,所以用一般的动态数组就可以了。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
 //It's an iterative way by two "while circles" to travesal every level of the tree, BFS actually, u can use queue to do it ,but it seems time will exceed
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> nodeData = new ArrayList<List<Integer>>();
        if(root==null)return nodeData;
        List<TreeNode> nodeList = new ArrayList<TreeNode>();
        nodeList.add(root);
        int start = 0;
        int last = 1; //value 1 is for the 0 level
        while(start<nodeList.size()){
            last = nodeList.size();//update the last value of the new level
            List<Integer> tempList = new ArrayList<Integer>(); //store the node data in every level
            while(start < last){
                TreeNode tempNode = (TreeNode)nodeList.get(start);
                if(tempNode!=null)
                tempList.add(tempNode.val);
                if(tempNode.left!=null)nodeList.add(tempNode.left);
                if(tempNode.right!=null)nodeList.add(tempNode.right);
                start++;
            } 
            nodeData.add(0,tempList);
        }
        
        return nodeData;
        
    }
}