二叉树题解方法

作者: ML李嘉图

各种树的数据结构

详情请见:https://www.cnblogs.com/zwtblog/p/15056076.html树

递归

确定下来递归算法的三个要素。每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!

  1. 确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

二叉树的递归遍历

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    ArrayList<Integer> preOrderReverse(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        preOrder(root, result);
        return result;
    }
    void preOrder(TreeNode root, ArrayList<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);           // 注意这一句
        preOrder(root.left, result);
        preOrder(root.right, result);
    }
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }
    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}

二叉树的迭代遍历

// 前序遍历顺序:中-左-右,入栈顺序:中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}
// 中序遍历顺序: 左-中-右 入栈顺序: 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}
// 后序遍历顺序 左-右-中 入栈顺序:中-左-右 出栈顺序:中-右-左, 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

二叉树的统一迭代法

愿称之为:大统一定律 针对三种遍历方式,使用迭代法是可以写出统一风格的代码!

迭代法前序遍历代码如下:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点(空节点不入栈)
                if (node.left!=null) st.push(node.left);    // 添加左节点(空节点不入栈)
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。

                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

迭代法中序遍历代码如下:

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
    Stack<TreeNode> st = new Stack<>();
    if (root != null) st.push(root);
    while (!st.empty()) {
        TreeNode node = st.peek();
        if (node != null) {
            st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
            if (node.right!=null) st.push(node.right);  // 添加右节点(空节点不入栈)
            st.push(node);                          // 添加中节点
            st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。
            if (node.left!=null) st.push(node.left);    // 添加左节点(空节点不入栈)
            st.pop();           // 将空节点弹出
            node = st.peek();    // 重新取出栈中元素
            st.pop();
            result.add(node.val); // 加入到结果集
        }
    }
    return result;
}
}

迭代法后序遍历代码如下:

class Solution {
   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点(空节点不入栈)
                if (node.left!=null) st.push(node.left);    // 添加左节点(空节点不入栈)         

                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
   }
}

二叉树的层序遍历

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。 而这种层序遍历方式就是图论中的广度优先遍历,只不过们应用在二叉树上。

使用队列实现二叉树广度优先遍历,动画如下:

// 102.二叉树的层序遍历
class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        //checkFun01(root,0);
        checkFun02(root);
        return resList;
    }
    //DFS--递归方式
    public void checkFun01(TreeNode node, Integer deep) {
        if (node == null) return;
        deep++;
        if (resList.size() < deep) {
            //当层级增加时,list的Item也增加,利用list的索引值进行层级界定
            List<Integer> item = new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep - 1).add(node.val);
        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }
    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);
        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();
            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);
                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }
            resList.add(itemList);
        }
    }
}

翻转二叉树

注意只要把每一个节点的左右孩子翻转一下,就可以达到整体翻转的效果 这道题目使用前序遍历和后序遍历都可以,唯独中序遍历不方便,因为中序遍历会把某些节点的左右孩子翻转了两次!

那么层序遍历可以不可以呢?依然可以的!只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的!

递归法

们来看一下递归三部曲:

  1. 确定递归函数的参数和返回值

参数就是要传入节点的指针,不需要其他参数了,通常此时定下来主要参数,如果在写递归的逻辑中发现还需要其他参数的时候,随时补充。

返回值的话其实也不需要,但是题目中给出的要返回root节点的指针,可以直接使用题目定义好的函数,所以就函数的返回类型为TreeNode*

TreeNode* invertTree(TreeNode* root)
  1. 确定终止条件

当前节点为空的时候,就返回

if (root == NULL) return root;
  1. 确定单层递归的逻辑

因为是先前序遍历,所以先进行交换左右孩子节点,然后反转左子树,反转右子树。

swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);

迭代法

//DFS递归
class Solution {
   /**
     * 前后序遍历都可以
     * 中序不行,因为先左孩子交换孩子,再根交换孩子(做完后,右孩子已经变成了原来的左孩子),再右孩子交换孩子(此时其实是对原来的左孩子做交换)
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);
        return root;
    }
    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}
//BFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {return null;}
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.poll();
                swap(node);
                if (node.left != null) {deque.offer(node.left);}
                if (node.right != null) {deque.offer(node.right);}
            }
        }
        return root;
    }
    public void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

对称二叉树

给定一个二叉树,检查它是否是镜像对称的。

对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了其实们要比较的是两个树(这两个树是根节点的左右子树),所以在递归遍历的过程中,也是要同时遍历两棵树。

递归法

递归三部曲

  1. 确定递归函数的参数和返回值

因为们要比较的是根节点的两个子树是否是相互翻转的,进而判断这个树是不是对称树,所以要比较的是两个树,参数自然也是左子树节点和右子树节点。

返回值自然是bool类型。

代码如下:

bool compare(TreeNode* left, TreeNode* right)
  1. 确定终止条件

要比较两个节点数值相不相同,首先要把两个节点为空的情况弄清楚!否则后面比较数值的时候就会操作空指针了。

节点为空的情况有:(注意们比较的其实不是左孩子和右孩子,所以如下称之为左节点右节点

  • 左节点为空,右节点不为空,不对称,return false
  • 左不为空,右为空,不对称 return false
  • 左右都为空,对称,返回true

此时已经排除掉了节点为空的情况,那么剩下的就是左右节点不为空:

  • 左右都不为空,比较节点数值,不相同就return false

此时左右节点不为空,且数值也不相同的情况们也处理了。

代码如下:

if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false; // 注意这里没有使用else

注意上面最后一种情况,没有使用else,而是elseif, 因为们把以上情况都排除之后,剩下的就是 左右节点都不为空,且数值相同的情况。

  1. 确定单层递归的逻辑

此时才进入单层递归的逻辑,单层递归的逻辑就是处理 左右节点都不为空,且数值相同的情况。

  • 比较二叉树外侧是否对称:传入的是左节点的左孩子,右节点的右孩子。
  • 比较内测是否对称,传入左节点的右孩子,右节点的左孩子。
  • 如果左右都对称就返回true ,有一侧不对称就返回false 。

代码如下:

bool outside = compare(left->left, right->right);   // 左子树:左、 右子树:右
bool inside = compare(left->right, right->left);    // 左子树:右、 右子树:左
bool isSame = outside && inside;                    // 左子树:中、 右子树:中(逻辑处理)
return isSame;

如上代码中,们可以看出使用的遍历方式,左子树左右中,右子树右左中,所以把这个遍历顺序也称之为"后序遍历”(尽管不是严格的后序遍历)。

 /**
     * 递归法
     */
    public boolean isSymmetric1(TreeNode root) {
        return compare(root.left, root.right);
    }
    private boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right != null) {
            return false;
        }
        if (left != null && right == null) {
            return false;
        }
        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) {
            return false;
        }
        // 比较外侧
        boolean compareOutside = compare(left.left, right.right);
        // 比较内侧
        boolean compareInside = compare(left.right, right.left);
        return compareOutside && compareInside;
    }

迭代法

使用队列

这里们可以使用队列来比较两个树(根节点的左右子树)是否相互翻转,(注意这不是层序遍历

使用栈

 /**
     * 迭代法
     * 使用双端队列,相当于两个栈
     */
    public boolean isSymmetric2(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root.left);
        deque.offerLast(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.pollFirst();
            TreeNode rightNode = deque.pollLast();
            if (leftNode == null && rightNode == null) {
                continue;
            }
//            if (leftNode == null && rightNode != null) {
//                return false;
//            }
//            if (leftNode != null && rightNode == null) {
//                return false;
//            }
//            if (leftNode.val != rightNode.val) {
//                return false;
//            }
            // 以上三个判断条件合并
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            deque.offerFirst(leftNode.left);
            deque.offerFirst(leftNode.right);
            deque.offerLast(rightNode.right);
            deque.offerLast(rightNode.left);
        }
        return true;
    }
    /**
     * 迭代法
     * 使用普通队列
     */
    public boolean isSymmetric3(TreeNode root) {
        Queue<TreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }
//            if (leftNode == null && rightNode != null) {
//                return false;
//            }
//            if (leftNode != null && rightNode == null) {
//                return false;
//            }
//            if (leftNode.val != rightNode.val) {
//                return false;
//            }
            // 以上三个判断条件合并
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            // 这里顺序与使用Deque不同
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }
        return true;
    }

二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

迭代法

使用迭代法的话,使用层序遍历是最为合适的,因为最大的深度就是二叉树的层数,和层序遍历的方式极其吻合。

在二叉树中,一层一层的来遍历二叉树,记录一下遍历的层数就是二叉树的深度,如图所示:

class solution {
    /**
     * 递归法
     */
    public int maxdepth(treenode root) {
        if (root == null) {
            return 0;
        }
        int leftdepth = maxdepth(root.left);
        int rightdepth = maxdepth(root.right);
        return math.max(leftdepth, rightdepth) + 1;
    }
}
class solution {
    /**
     * 迭代法,使用层序遍历
     */
    public int maxdepth(treenode root) {
        if(root == null) {
            return 0;
        }
        deque<treenode> deque = new linkedlist<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isempty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                treenode poll = deque.poll();
                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
        }
        return depth;
    }
}

n叉树的最大深度

class solution {
    /**
     * 迭代法,使用层序遍历
     */
    public int maxDepth(Node root) {
        if (root == null)   return 0;
        int depth = 0;
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty())
        {
            depth ++;
            int len = que.size();
            while (len > 0)
            {
                Node node = que.poll();
                for (int i = 0; i < node.children.size(); i++)
                    if (node.children.get(i) != null) 
                        que.offer(node.children.get(i));
                len--;
            }
        }
        return depth;
    }
}

二叉树的最小深度

更新中…………

原文创作:ML李嘉图

原文链接:https://www.cnblogs.com/zwtblog/p/15254462.html

文章列表

更多推荐

更多
  • 面试AI技术内参-031经典搜索核心算法:TF 031 经典搜索核心算法:TF-IDF及其变种先来介绍TF-IDF算法。 在信息检索(Information Retrieval)、文本挖掘(Text Mining)以及自然语言处理(Natural Language Processi
  • 面试AI技术内参-004精读2017年EMNLP最佳长论文之一 004 精读2017年EMNLP最佳长论文之一irical Methods in Natural Language Processing),是由国际计算语言学协会**ACL** (Association for Computationa
  • 面试AI技术内参-126复盘5计算机视觉核心技术模块 126复盘 5 计算机视觉核心技术模块 复盘 5 计算机视觉核心技术模块 今模块里,我们一起学习了12期内容,讨论了四个话题,这些话题主要围绕计算机视觉的基础知识和深度学习技术在这个领域的应用。 之所以这么安排,是因为没有深度学
  • 面试AI技术内参-037查询关键字理解三部曲之分类 037 查询关键字理解三部曲之分类技术和基于机器学习的排序算法(Learning to Rank)。 经典的信息检索技术为2000年之前的搜索引擎提供了基本的算法支持。从中衍生出的TF-IDF、BM25还有语言模型(Language
  • 面试AI技术内参-019SIGIR2018论文精读:偏差和流行度之间的关系 019 SIGIR 2018论文精读:偏差和流行度之间的关系2日在美国密歇根州的安娜堡举行。从今天开始,我将精选几篇大会上最有价值的论文,和你一起来读。 我先简单介绍一下这个大会。SIGIR从1978年开始举办,有40年的历史,是信息
  • 面试AI技术内参-022CVPR2018论文精读:如何研究计算机视觉任务之间的关系? 022 CVPR 2018论文精读:如何研究计算机视觉任务之间的关系?PR(Conference on Computer Vision and Pattern Recognition),在美国的盐湖城举行。CVPR大会从1985年开始举
  • 面试AI技术内参-021SIGIR2018论文精读:如何对搜索页面上的点击行为进行序列建模? 021 SIGIR 2018论文精读:如何对搜索页面上的点击行为进行序列建模? 我们已经分享了SIGIR 2018的最佳论文,介绍了如何对推荐系统中的偏差进行建模,从而能够利用这种对偏差的理解,来更加准确地对待基于流行度的推荐结果。周
  • 面试AI技术内参-024CVPR2018论文精读:如何解决排序学习计算复杂度高这个问题? 024 CVPR 2018论文精读:如何解决排序学习计算复杂度高这个问题?于排序的损失函数的有效优化》(Efficient Optimization for Rank-based Loss Functions)。 还是先简单介绍下论文
  • 面试AI技术内参-061基于隐变量的模型之一:矩阵分解 061 基于隐变量的模型之一:矩阵分解 -内容特征的推荐模型。 这周,我们来看一类非常重要的推荐模型:**基于隐变量的推荐模型**。这类模型的优势是对用户和物品信息中的隐含结构进行建模,从而能够挖掘更加深层次的用户和物品关系。 什么
  • 面试AI技术内参-107基于门机制的RNN架构:LSTM与GRU 107 基于门机制的RNN架构:LSTM与GRU -地利用了文字的序列信息,从而能够对文本进行大规模的建模。在上一次的分享里,我们聊了对序列建模的深度学习利器"递归神经网络",或简称RNN。我们分析了文本信息中的序列数据,了解了如何对文
  • 近期文章

    更多
    文章目录

      推荐作者

      更多