LeetCode199之二叉樹的右視圖(二叉樹的深度周遊和廣度周遊)LeetCode103二叉樹的鋸齒形層次周遊(相關話題：二叉樹、層次周遊)

題目描述

給定一個二叉樹的 根節點 root，想象自己站在它的右側，按照從頂部到底部的順序，傳回從右側所能看到的節點值。

示例 1:

輸入: [1,2,3,null,5,null,4]

輸出: [1,3,4]

示例 2:

輸入: [1,null,3]

輸出: [1,3]

示例 3:

輸入: []

輸出: []

思路分析

這題如果沒有接觸過二叉樹的深度周遊和廣度周遊其實是很難自己做出來的

下面闡述下思考的過程：

需要一個棧nodeStack （隊列nodeQueue ）來記錄二叉樹的深度(廣度)周遊結果

需要一個棧depthStack （隊列depthQueue ）來記錄和二叉樹的深度(廣度)周遊節點相對應的深度

需要一個哈希表rightmostValueAtDepth 來記錄每個深度最右側節點的值

基本的代碼架構如下：

Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();


Stack<TreeNode> nodeStack = new Stack<TreeNode>();
Stack<Integer> depthStack = new Stack<Integer>();
nodeStack.push(root);
depthStack.push(0);

while (!nodeStack.isEmpty()) {
     TreeNode node = nodeStack.pop();
     int depth = depthStack.pop();

    if (node != null) {

        nodeStack.push(node.left);
        nodeStack.push(node.right);
        depthStack.push(depth + 1);
        depthStack.push(depth + 1);
    }
}
           

Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();


Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
Queue<Integer> depthQueue = new LinkedList<Integer>();
nodeQueue.add(root);
depthQueue.add(0);

while (!nodeQueue.isEmpty()) {
      TreeNode node = nodeQueue.remove();
      int depth = depthQueue.remove();

      if (node != null) {

          nodeQueue.add(node.left);
          nodeQueue.add(node.right);
          depthQueue.add(depth + 1);
          depthQueue.add(depth + 1);
      }
}           

兩處代碼最核心的差異在于

深度周遊用棧保證每個深度第一次通路到的資料一定是最右側的（見下面代碼）

// 如果不存在對應深度的節點我們才插入
if (!rightmostValueAtDepth.containsKey(depth)) {
    rightmostValueAtDepth.put(depth, node.val);
}

            

廣度周遊用隊保證每個深度第後次通路到的資料一定是最右側的（見下面代碼）

// 由于每一層最後一個通路到的節點才是我們要的答案，是以不斷更新對應深度的資訊即可
 rightmostValueAtDepth.put(depth, node.val);

            

代碼實作

方法一（深度優先）

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;

        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> depthStack = new Stack<Integer>();
        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int depth = depthStack.pop();

            if (node != null) {
            	// 維護二叉樹的最大深度
                max_depth = Math.max(max_depth, depth);

                // 如果不存在對應深度的節點我們才插入
                if (!rightmostValueAtDepth.containsKey(depth)) {
                    rightmostValueAtDepth.put(depth, node.val);
                }

                nodeStack.push(node.left);
                nodeStack.push(node.right);
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }

        List<Integer> rightView = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) {
            rightView.add(rightmostValueAtDepth.get(depth));
        }

        return rightView;
    }
}
           

方法二（廣度優先，層次周遊）

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;

        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> depthQueue = new LinkedList<Integer>();
        nodeQueue.add(root);
        depthQueue.add(0);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();
            int depth = depthQueue.remove();

            if (node != null) {
            	// 維護二叉樹的最大深度
                max_depth = Math.max(max_depth, depth);

                // 由于每一層最後一個通路到的節點才是我們要的答案，是以不斷更新對應深度的資訊即可
                rightmostValueAtDepth.put(depth, node.val);

                nodeQueue.add(node.left);
                nodeQueue.add(node.right);
                depthQueue.add(depth + 1);
                depthQueue.add(depth + 1);
            }
        }

        List<Integer> rightView = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) {
            rightView.add(rightmostValueAtDepth.get(depth));
        }

        return rightView;
    }
}