LeetCode：二叉树小结

LeetCode：二叉树小结

LeetCode：二叉树小结

• 说明
• 递归遍历
• 前序迭代遍历——leetcode：144
• 中序迭代遍历——leetcode：94
• 后序序迭代遍历——leetcode：145
• 层次遍历——leetcode：102

说明

此文章记录LeetCode中前序，中序，后序迭代遍历以及层次遍历，说明并不是很多，更多的可能是方便自己回顾，如果对您有所帮助，更是欣喜。
前中后都可以进行递归编写，因此迭代遍历肯定需要借助栈来完成，因为递归的本质就是栈。层次遍历有所不同，需要队列来完成，它的实质是广度优先遍历。

递归遍历

比较简单，以前序为例，其他的仅仅改变helper中res.add的位置即可

class Solution {
    List res = new linkedList<>();
    public List preorderTraversal(TreeNode root) {
        if (root!=null) helper(root);
        return res;
    }
    public List helper(TreeNode root){
        res.add(root.val);
        if (root.left!=null) helper(root.left);
        if (root.right!=null) helper(root.right);
        return res;
    }
}

前序迭代遍历——leetcode：144

class Solution {
    public List preorderTraversal(TreeNode root) {
        Deque stack = new linkedList<>();
        List res = new ArrayList<>();
        if (root==null) return res;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right!=null) stack.push(node.right);
            if (node.left!=null) stack.push(node.left);
        }
        return res;
    }
}

中序迭代遍历——leetcode：94

class Solution {
    public List inorderTraversal(TreeNode root) {
        Deque stack = new linkedList<>();
        List src = new ArrayList<>();
        while (!stack.isEmpty()||root!=null){
            if (root != null){
                stack.push(root);
                root = root.left;
            }else{
                root = stack.pop();
                src.add(root.val);
                root = root.right;
            }
        }
        return src;
    }
}

后序序迭代遍历——leetcode：145

这里需要稍稍说明一下，这里的后序遍历是由前序遍历变来的：
后序遍历中遍历的顺序是左右中，而前序的顺序是中左右，如果我们改变一下左右结点进栈的顺序，就会变成中右左（这个没有实际的意义），接着我们只要倒序便可以完成左右中，及后序遍历，其中倒序可以通过linkedList中addFirst来完成，当然也可以通过Collections.reverse()来完成，我这里用的是addFirst；

class Solution {
    public List postorderTraversal(TreeNode root) {
        Deque stack = new linkedList<>();
        //List中不可以使用addFirst，所以只能用linkedList声明
        linkedList src = new linkedList<>();
        if (root==null) return src;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            src.addFirst(node.val);
            if (node.left!=null) stack.push(node.left);
            if (node.right!=null) stack.push(node.right);
        }
        return src;
    }
}

层次遍历——leetcode：102

class Solution {
    public List> levelOrder(TreeNode root) {
        Queue queue = new linkedList<>();
        List> res = new ArrayList<>();
        if (root==null) return res;
        queue.add(root);
        while(!queue.isEmpty()){
            linkedList tem = new linkedList<>();
            for (int i=queue.size();i>0;i--){
                TreeNode node = queue.poll();
                tem.add(node.val);
                if (node.left!=null) queue.add(node.left);
                if (node.right!=null) queue.add(node.right);
            }
            res.add(tem);
        }
        return res;
    }
}