Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

二叉树的右视图

Posted on In , ,
Symbols count in article: 3k Reading time ≈ 3 mins.

来源Leetcode第199题二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

1
2
3
4
5
6
7
8
9
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

错误的遍历

第一次提交忽略了当右子树比左子树短的情况下，要对左子树进行遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
List<Integer> ans = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
    if(root == null)
        return ans;
    helper(root);
    return ans;
}

public void helper(TreeNode root){
    if(root != null)
        ans.add(root.val);
    if(root.right != null)
        helper(root.right);
    else if(root.left != null)
        helper(root.left);
    return;
}

队列

既然要考虑所有情况，那么就进行层序遍历，然后保留最后一个进队列的节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if(root == null)
        return ans;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()){
        int len = queue.size();
        for(int i = 0 ; i < len ; i++){
            if(i == len - 1)
                ans.add(queue.peek().val);
            TreeNode tmp = queue.remove();
            if(tmp.left != null)
                queue.add(tmp.left);
            if(tmp.right != null)
                queue.add(tmp.right);
        }
    }
    return ans;
}

深度优先搜索

来源题解

直觉

如果按正确的顺序访问每个节点，就可以有效地获得二叉树的右视图。

算法

上面提到的顺序之一可以由深度优先搜索定义。在深度优先搜索中，我们总是先访问右子树。这样就保证了当我们访问树的某个特定深度时，我们正在访问的节点总是该深度的最右侧节点。于是，可以存储在每个深度访问的第一个结点，一旦我们知道了树的层数，就可以得到最终的结果数组。

image.png

上图表示了问题的一个实例。红色结点自上而下组成答案，边缘以访问顺序标号。

题解通过维护两个栈（一个深度栈，一个节点栈）栈以及一个HashMap来填充每层的右视图。通过左子树入栈在右子树入栈的顺序保证出栈时是右子树先出栈，在将其对应深度填到HashMap里，最后按照深度对Map做一次遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;

        /* These two stacks are always synchronized, providing an implicit
         * association values with the same offset on each stack. */
        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);

                /* The first node that we encounter at a particular depth contains
                * the correct value. */
                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);
            }
        }

        /* Construct the solution based on the values that we end up with at the
         * end. */
        List<Integer> rightView = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) {
            rightView.add(rightmostValueAtDepth.get(depth));
        }

        return rightView;
    }
}

递归

既然题解里用深度标明了每层的元素，那么我也应该可以在递归时多传一个参数，记作是当前节点的深度值，按照右左的顺序递归即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List<Integer> ans = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
    if(root == null)
        return ans;
    helper(root,0);
    return ans;
}

public void helper(TreeNode root,int deepth){
    if(root == null)
        return;
    if(deepth == ans.size())
        ans.add(root.val);
    if(root.right != null)
        helper(root.right,deepth + 1);
    if(root.left != null)
        helper(root.left,deepth + 1);
    return;
}