算法总结

1.二叉树的右侧视图

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

题解：根之前二叉树解题类似，用广度优先搜索或者深度优先搜索遍历二叉树，这个题就是取每一层的最后一个元素，使用一个队列存储每一层的结点完成对层结点遍历

package com.chenghaixiang.jianzhi2.day15;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author 程海翔
 * @school 石家庄铁道大学
 */
public class Office046 {
}
//给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
//即取每一层的最后一个元素
class Solution02 {
    public List<Integer> rightSideView(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
            //队列存储每一层的结点
            //初始化添加根结点
            queue.add(root);
        }
        List<Integer> res=new LinkedList<>();

        while (!queue.isEmpty()){
            //获取当前层中结点个数
            int lg=queue.size();
            //遍历队列
            for(int i=0;i<lg;i++){
                TreeNode q=queue.poll();
                //取每一层的最后一个结点
                if(i==lg-1){
                    res.add(q.val);
                }
                if(q.left!=null){
                    queue.add(q.left);
                }
                if(q.right!=null){
                    queue.add(q.right);
                }
            }
        }
        return res;
    }
}

View Code

2.二叉树剪枝

给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。

节点 node 的子树为 node 本身，以及所有 node 的后代。

题解： 这题很简单就是递归二叉树，将结点值为0，并且没有子树的结点删除

package com.chenghaixiang.jianzhi2.day16;

/**
 * @author 程海翔
 * @school 石家庄铁道大学
 */
public class Office047 {
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
//给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。
//
//节点 node 的子树为 node 本身，以及所有 node 的后代。
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if(root==null){
            return null;
        }
        root.left=pruneTree(root.left);
        root.right=pruneTree(root.right);
        //结点值为0，并且没有子树的结点删除
        if(root.right==null&&root.left==null&&root.val==0){
            return null;
        }
        return root;
    }
}

View Code