leetcode_199 Binary Tree Right Side View

题目：

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---

 /   \

2     3         <---

 \     \

  5     4       <---

You should return [1, 3, 4].

给出任意一颗二叉树，返回它的每层最右边的结点值集合。

思路：

考虑递归解决该问题。

首先判断根节点是否为空，为空的话直接返回空集合。

递归的获取左右子树的每层的最外侧结点的值集合，如果左边的值集合元素个数多于右边集合的，说明左子树的高度大于右子树的，需要把多的那部分元素加入到右子树的集合中。

代码：

     public static List<Integer> rightSideView(TreeNode root){

         List<Integer> arr1 = new ArrayList<Integer>();

         List<Integer> arr2 = new ArrayList<Integer>();

         //根节点为空返回空集合

         if(root == null){

             return arr1;

         }

         arr1.add(root.val);

         arr2.add(root.val);

         //获取左子树的每层最外侧结点值集合

         rightSideView(root.left, arr1);

         //获取右子树的每层最外侧结点值集合

         rightSideView(root.right, arr2);

         //如果左子树集合元素多于右子树，说明左子树高度大于右子树

         if(arr1.size() > arr2.size()){

             int num = arr2.size();

             for(int i = num; i < arr1.size(); i++){

                 arr2.add(arr1.get(i));

             }

         }

         return arr2;

     }

     //该函数是同样的思想，每次获取左右子树的每层最外侧结点值集合

     //如果左子树集合元素多于右子树，说明左子树高度大于右子树

     public static void rightSideView(TreeNode root, List<Integer> arr) {

         List<Integer> arr1 = new ArrayList<Integer>();

         List<Integer> arr2 = new ArrayList<Integer>();

         if(root == null){

             return;

         }

         arr1.add(root.val);

         arr2.add(root.val);

         rightSideView(root.left,arr1);

         rightSideView(root.right,arr2);

         if(arr1.size() > arr2.size()){

             int num = arr2.size();

             for(int i = num; i < arr1.size(); i++){

                 arr2.add(arr1.get(i));

             }

         }

         for(int i :arr2){

             arr.add(i);

         }

     }

巴特西

leetcode_199 Binary Tree Right Side View

最新文章

热门文章