94二叉树中序遍历.md

题目链接

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/

解法

方法一 : 递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> arr = new ArrayList<>();
        helper(root,arr);
        return arr;
    }
    //定义一个辅助函数
    public void helper(TreeNode root,List arr){
        if(root != null){
            if(root.left != null)
                helper(root.left,arr);
            arr.add(root.val);
            if(root.right != null)
                helper(root.right,arr);
        }
    }
}

吐槽:上周刷题由于接触项目,制定计划等等原因吧,中断了几天,这周一重新捡起来了,这道题是一道非常简单的题目,但是我在书写时的不熟练,还有第一遍写是居然忘记了中序遍历的顺序,足以看出我目前的问题的,就是眼高手低,所以还是需要仰望星空,脚踏实地的练习,可能我这个习惯像一些大佬吧,就是喜欢记录,喜欢打字抒发心里感觉,闲话少叙,下面说一些这个递归解法。

树的问题绝大部分都是使用递归解决的,关于遍历问题我更希望自己能够把这个当成一个模板来记忆,首先就是如果不使用辅助函数helper的话,那么每一次递归都需要创建ArrayList数组,造成空间上的浪费,自己开始写的时候居然把ArrayList定义在方法外面,这是一个非常差的习惯。


方法二:基于栈

这是一种基于栈的迭代算法,迭代就是前一次的输出作为下一次的饿输入,对应题目就是从栈里面弹出来的元素可以继续下一次的运行输入

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        TreeNode curr = root;
        while(curr != null || !stack.isEmpty()){
            while(curr != null){
                //一直找到最左最小的叶子节点
                stack.push(curr);
                curr = curr.left;
            }
            //出栈,并加入到res数组中
            //此时curr指针指向null,调整一下
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

吐槽:

这种基于栈的方法也是非常的巧妙,是自己之前从来没有接触过的,每一次训练都会有收获的,让其他忧虑干扰都走远吧,自己心静下来,脚踏实地走,不要浮躁。真的是非常喜欢markdown这种格式的文本,真的是太舒服,以后技术总结文章就要这么写。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/94二叉树中序遍历md