94. Binary Tree Inorder Traversal 做题报告

题目链接:

       94. Binary Tree Inorder Traversal

题目大意:

        二叉树的中序遍历

做题报告:

(1)该题涉及的算法,数据结构以及相关知识点

        递归

(2)自己的解答思路+代码+分析时间和空间复杂度

       递归思路

/**
 * 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> ans = new ArrayList<Integer>();
        help(root,ans);
        return ans;
    }
    public void help(TreeNode root,List<Integer> ans) {
        if(root==null) return;
        if(root.left != null)  help(root.left,ans);
        ans.add(root.val);
        if(root.right != null)  help(root.right,ans);
    }
}

时间复杂度:O(n)  递归函数 T(n)=2⋅T(n/2)+1
空间复杂度:最坏情况下需要空间O(n),平均情况为O(log⁡n)

(3)经典解答思路+代码+分析时间和空间复杂度

方法一:递归

方法二:基于栈的遍历

注明:可看官方题解,有动画PPT

public 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;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}
作者:LeetCode
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法三:莫里斯遍历

方法四:颜色标记法

其核心思想如下:
    使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色。
    如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈。
    如果遇到的节点为灰色,则将节点的值输出。



class Solution {
    class ColorNode {
        TreeNode node;
        String color;
        
        public ColorNode(TreeNode node,String color){
            this.node = node;
            this.color = color;
        }
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<Integer>();
            
        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();
        stack.push(new ColorNode(root,"white"));
        
        while(!stack.empty()){
            ColorNode cn = stack.pop();
            if(cn.color.equals("white")){
                if(cn.node.right != null) stack.push(new ColorNode(cn.node.right,"white"));
                stack.push(new ColorNode(cn.node,"gray"));//gray标记该节点写入了答案列表
                if(cn.node.left != null) stack.push(new ColorNode(cn.node.left,"white"));
            }else{
                res.add(cn.node.val);
            }
        }
        return res;
    }
}


(4)比较自己想的和参考答案的区别

          用栈与递归这种思路,递归效率不高,栈迭代方法虽然提高了效率,但其嵌套循环却非常烧脑,不易理解,容易造成“一看就懂,一写就废”的窘况。而且对于不同的遍历顺序(前序、中序、后序),循环结构差异很大,更增加了记忆负担。比较推荐第四种解法。

上一篇:PHP中magic_quotes_gpc动态关闭无效的问题


下一篇:2. Add Two Numbers [Medium]