10 二叉树

二叉树遍历

第10节.pptx

题目1：递归方式实现二叉树先序、中序、后序遍历

// 先序打印 头-左-右
public static void pre(TreeNode head) {
    if (head == null) {
        return;
    }
    System.out.print(head.val + " ");
    pre(head.left);
    pre(head.right);
}
// 中序打印 左-头-右
public static void in(TreeNode head) {
    if (head == null) {
        return;
    }
    in(head.left);
    System.out.print(head.val + " ");
    in(head.right);
}
// 后序打印 左-右-头
public static void pos(TreeNode head) {
    if (head == null) {
        return;
    }
    pos(head.left);
    pos(head.right);
    System.out.print(head.val + " ");
}

题目2 非递归方式实现二叉树先序、中序、后序遍历

// 先序 头-左-右
public static void pre(TreeNode head) {
    if (head == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(head);
    while (!stack.empty()) {
        head = stack.pop();
        if (head.right != null) {
            stack.push(head.right);
        }
        if (head.left != null) {
            stack.push(head.left);
        }
        System.out.print(head.val + " ");
    }
}
// 中序 左 头 右
public static void in1(TreeNode head) {
    if (head == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    pushLeft(stack, head);
    while (!stack.empty()) {
        head = stack.pop();
        System.out.print(head.val + " ");
        if (head.right != null) {
            pushLeft(stack, head.right);
        }
    }
}
private static void pushLeft(Stack<TreeNode> stack, TreeNode head) {
    stack.push(head);
    while (head.left != null) {
        stack.push(head.left);
        head = head.left;
    }
}
public static void in2(Node cur) {
        System.out.print("in-order: ");
        if (cur != null) {
            Stack<Node> stack = new Stack<Node>();
            while (!stack.isEmpty() || cur != null) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    System.out.print(cur.value + " ");
                    cur = cur.right;
                }
            }
        }
        System.out.println();
    }
// 后序 左 右 头
public static void pos1(TreeNode head) {
    if (head == null) {
        return;
    }
    Stack<TreeNode> s1 = new Stack<>();
    Stack<TreeNode> s2 = new Stack<>();
    s1.push(head);
    while (!s1.isEmpty()) {
        // 头 右 左
        head = s1.pop();
        s2.push(head);
        if (head.left != null) {
            s1.push(head.left);
        }
        if (head.right != null) {
            s1.push(head.right);
        }
    }
    // 左 右 头
    while (!s2.isEmpty()) {
        System.out.print(s2.pop().val + " ");
    }
    System.out.println();
}
public static void pos2(TreeNode head) {
    if (head == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(head);
    TreeNode cur = null;
    while (!stack.isEmpty()) {
        cur = stack.peek();
        if (cur.left != null && head != cur.left && head != cur.right) {
            stack.push(cur.left);
        } else if (cur.right != null && head != cur.right) {
            stack.push(cur.right);
        } else {
            System.out.print(stack.pop().val + " ");
            head = cur;
        }
    }
    System.out.println();
}

附加题

给一个二叉树的先序遍历结果集，其中一个节点x
给这个二叉树的后序遍历结果集，其中一个节点x
求证明：先序遍历结果集中x前面的节点与后序遍历结果集中x后面的节点的交集是x全部的祖先节点、ppt
证明：

1. 先序遍历结果集，x的全部祖先节点在x前面；后序遍历结果集，x全部祖先节点在
2. x为左边节点
   1. x为最左边节点

先序结果集，x前面只有x的祖先节点，因此和后序遍历结果集的交集为全部祖先节点

1. x为中间左边节点

先序结果集，x前面包含x祖先节点和祖先左子树节点；
后序结果集，x后面包含x主线节点和祖先右子树节点
因此，交集只有全部祖先节点

1. x为右边节点

   1. x为最右边节点

   后序结果集，x后面只有x的祖先节点，因此和先序遍历结果集的交集为全部祖先节点

   1. x为中间有边节点

先序结果集，x前面包含x祖先节点和祖先左子树节点；
后序结果集，x后面包含x祖先节点和祖先右子树节点；
因此，交集只有全部祖先节点