Binary Tree Level Order Traversal II (DFS and BFS)

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]
]

 

方法一、方法和Binary Tree Level Order Traversal I 是大致相同的,只是在存储二叉树的一层节点作为的链表的时候,是插入到头部,输出的时候就是逆序了。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

     public LinkedList<LinkedList<Integer>> levelOrderBottom(TreeNode root) {
            LinkedList<LinkedList<Integer>> l = new LinkedList<LinkedList<Integer>>();
            LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//用来存x层的节点
            LinkedList<TreeNode> childQueue = new LinkedList<TreeNode>();//用来存x层节点的孩子节点

            if (root == null ) return l;
            if (queue.isEmpty()) {//先把root节点放入队列中
                queue.add(root);
            }
            while (!queue.isEmpty()) {//队列不为空,那么排空queue队列,并把queue队列中节点的孩子存储在childQueue队列中
                LinkedList<Integer> t = new LinkedList<Integer>();//用来存储借点中获取的值
                

                while (!queue.isEmpty()) {
                    TreeNode n = queue.remove();
                    t.add(n.val);

                    if (n.left != null)
                        childQueue.add(n.left);
                    if (n.right != null)
                        childQueue.add(n.right);
                }
                //l.add(t);//t加入到l中
                l.addFirst(t);//插入到l的头部

                queue.clear();//清除queue队列
                queue = new LinkedList<TreeNode>(childQueue);//queue指向 用queue队列中节点的孩子组成的队列
                childQueue.clear();//孩子队列清空

            }
            return l;

        }
}

 方法二、深度遍历。c++,code by stellari

vector<vector<int> > res;

void DFS(TreeNode* root, int level)
{
    if (root == NULL) return;
    if (level == res.size()) // The level does not exist in output
    {
        res.push_back(vector<int>()); // Create a new level
    }

    res[level].push_back(root->val); // Add the current value to its level
    DFS(root->left, level+1); // Go to the next level
    DFS(root->right,level+1);
}

vector<vector<int> > levelOrderBottom(TreeNode *root) {
    DFS(root, 0);
    return vector<vector<int> > (res.rbegin(), res.rend());
}
Tagged on: , , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>