( Leetcode 刷题)二叉树的前序、中序、后序遍历、N叉树的后序遍历

题目相关

题目要求为给定一个二叉树，返回相应的前序、中序、后序遍历。
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历

前序遍历

解法1 递归

/**
 * 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> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        QX(root, list);
        return list;
    }
    //前序遍历是根-左-右的顺序
    public void QX(TreeNode root, List<Integer> list) {
        if (root != null) {
            list.add(root.val);
            if (root.left != null) {
                QX(root.left, list);
            }
            if (root.right != null) {
                QX(root.right, list);
            }
        }
    }
}

解法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> preorderTraversal(TreeNode root) {
        //定义一个存放树结点的栈、用于保存遍历结果的list和指向当前结点的变量curr
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        TreeNode curr = root;
        
        //只有当栈为空且当前结点为NULL时才是遍历结束，其余情况都为遍历中
        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                //前序遍历先将根结点的值放入list
                list.add(curr.val);
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            curr = curr.right;
        }
        return list;
    }
}

解法3 莫里斯遍历

莫里斯遍历的步骤为：

  1. 当前结点指向根结点，判断二叉树的根结点有没有左子树，没有则存储该根结点的值，当前结点变为根结点的右孩子。
  2. 如果第一步中有左子树，判断整个左子树中最右边的结点的右孩子是不是null
    2.1 是null，存储当前节点的值，将该结点的右孩子指向当前结点，再将当前结点更新为当前结点的左孩子
    2.2 是当前节点，证明该结点与当前结点已经建立了连接，拆除连接恢复树结构，再将当前结点更新为当前结点的右孩子。

重复上述算法直到当前结点为null。

/**
 * 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> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode curr = root;

        //算法结束条件为当前节点为null
        while (curr != null) {
            //if语句判断算法第一步
            if (curr.left == null) {
                list.add(curr.val);
                curr = curr.right;
            } else {
                //while循环与第一个if为算法的2.1，循环将pre指向左子树的最右结点
                TreeNode pre = curr.left;
                while (pre.right != null && pre.right != curr) {
                    pre = pre.right;
                }
                //pre的右孩子指向当前结点
                if (pre.right == null) {
                    pre.right = curr;
                    list.add(curr.val);
                    curr = curr.left;
                } else {
                    //算法的2.2
                    pre.right = null;
                    curr = curr.right;
                }

            }
        }
        return list;
    }
}

中序遍历

跟前序遍历主要是顺序差别

解法1 递归

/**
 * 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> list = new ArrayList<Integer>();
        ZX(root, list);
        return list;
    }
    
    //中序遍历：左-根-右
    public void ZX(TreeNode root, List<Integer> list) {
        if (root != null) {
            if (root.left != null) {
                ZX(root.left, list);
            }
            list.add(root.val);
            if (root.right != null) {
                ZX(root.right, list);
            }
        }
    }
}

解法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) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        TreeNode curr = root;


        while ((!stack.isEmpty()) || (curr != null)) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            //从最左边的结点开始
            list.add(curr.val);
            curr = curr.right;
        }
        return list;
    }
}

解法3 莫里斯遍历

/**
 * 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> list = new ArrayList<>();
        TreeNode curr = root;

        while (curr != null) {
            if (curr.left == null) {
                list.add(curr.val);
                curr = curr.right;
            } else {
                TreeNode pre = curr.left;
                while (pre.right != null && pre.right != curr) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = curr;
                    curr = curr.left;
                } else {
                    //跟前序遍历不同，中序遍历在第二次遇到结点时存储结点
                    pre.right = null;
                    list.add(curr.val);
                    curr = curr.right;
                }
            }
        }
        return list;
    }
}

后序遍历

解法1 递归

递归注意顺序就好。

/**
 * 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> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        HX(root, list);
        return list;
    }
    
    //后序遍历顺序为左-右-根
    public void HX(TreeNode root, List<Integer> list) {
        if (root != null) {
            if (root.left != null) {
                HX(root.left, list);
            }
            if (root.right != null) {
                HX(root.right, list);
            }
            list.add(root.val);
        }
    }
}

解法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> postorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        TreeNode curr = root;

        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                //先右子树
                list.add(curr.val);
                stack.push(curr);
                curr = curr.right;
            }
            curr = stack.pop();
            //再左子树
            curr = curr.left;
        }
        //逆序
        Collections.reverse(list);
        return list;
    }
}

再进一步，可以不用逆序输出，而是在存储结果的时候，不断地将结点插入到上一个存储的结点的前面，最后顺序输出结果也是后序遍历的顺序。在迭代的过程中，处理顺序还是根-右-左的顺序，但是存储时不断将结点放在上一个存储的结点前面，在list相当于完成了左-右-根的顺序。这个思路是对上面一版代码的优化，更为巧妙。

/**
 * 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> postorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> list = new LinkedList<>();
        TreeNode curr = root;

        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                //存储在上一个存储的结点前面
                list.addFirst(curr.val);
                stack.push(curr);
                curr = curr.right;
            }
            curr = stack.pop();
            curr = curr.left;
        }
        return list;
    }
}

那么在处理中就按照后序遍历的左-右-根顺序，可以吗？
自然是可以的，不过有几点值得注意的点，按照左-右-根的顺序遍历，必须保证左孩子和右孩子都已经被遍历过，并且左孩子在右孩子之前遍历才行。

/**
 * 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> postorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        TreeNode curr = root;
        TreeNode s = null;

        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            //peek()返回栈顶元素，不在栈中删除它
            curr = stack.peek();
            if (curr.right == null || curr.right == s) {
                list.add(curr.val);
                stack.pop();
                s = curr;
                curr = null;
            } else {
                curr = curr.right;
            }
        }
        return list;
    }
}

解法3 莫里斯遍历

与解法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> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode curr = root;

        while (curr != null) {
            if (curr.right == null) {
                list.add(curr.val);
                curr = curr.left;
            } else {
                TreeNode pre = curr.right;
                while (pre.left != null && pre.left != curr) {
                    pre = pre.left;
                }
                if (pre.left == null) {
                    pre.left = curr;
                    list.add(curr.val);
                    curr = curr.right;
                }
                if (pre.left == curr) {
                    pre.left = null;
                    curr = curr.left;
                }
            }
        }
        Collections.reverse(list);
        return list;
    }
}

题目描述

给定一个N叉树，返回其节点值的后序遍历。
590. N叉树的后序遍历

解法 迭代

思路是根-右-左，最后逆序得到后序遍历。

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<Integer> postorder(Node root) {
        Stack<Node> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        stack.add(root);
        while(!stack.isEmpty()){
            Node curr = stack.pop();
            //把这个节点的所有孩子加入栈中，因为栈先进后出，所有下次pop()得到的是最右边的孩子，符合根-右-左的顺序
            for( Node child : curr.children){
                if(child != null){
                    stack.add(child);
                }
            }
            list.add(curr.val);
        } 
        //逆序一下
        Collections.reverse(list);
        return list;
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。