二叉树算法_C/C++/C#

二叉树遍历前序遍历

class Solution {
    List list = new ArrayList<>();
    public List preorderTraversal(TreeNode root) {
        preOrder1(root);
        return list;
    }

    public void preOrder(TreeNode root){
        if(root == null) return;
        list.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    // 非递归
    public void preOrder1(TreeNode root){
        if(root == null) return;
        Stack stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop(); // root先出栈，然后根据栈后入先出，所以下一个出的是左
            list.add(root.val);

            // 右入栈
            if(root.right != null) {
                stack.push(root.right);
            }
            // 左入栈
            if(root.left != null) {
                stack.push(root.left);
            }

        }
    }
}

中序遍历

class Solution {
    public List inorderTraversal(TreeNode root) {
        List list = new ArrayList<>();
//        inorder(root, list); // 递归
        inorder1(root, list);  // 非递归
        return  list;

    }

    public void inorder(TreeNode root, List list){
        if(root==null) return;
        inorder(root.left, list);
        list.add(root.val);// 递归 中序遍历
        inorder(root.right, list);
    }

    // 迭代的方式解决
    // 用栈  左中右（左中）
    public void inorder1(TreeNode root, List list){
        if(root == null) return;
        Stack stack = new Stack<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {// || node != null
            while (node != null) {
                stack.push(node);
                node = node.left; // while循环：先填入所有左节点
            }
            node = stack.pop(); // 弹出时，值加入res
             res.add(node.val);
            node = node.right; // 右节点
        }
    }

}

后序遍历

class Solution {
    List list = new ArrayList<>();
    public List postorderTraversal(TreeNode root) {
        postOrder(root);
        return list;
    }

    public void postOrder(TreeNode root){
        if(root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        list.add(root.val);
    }
    // 相对前序非递归遍历，要用两个栈
    // s1入栈: 头 左 右  s2入栈：头 右 左
    // 出栈：左，右，头
    public void postOrder1(TreeNode root){
        if(root == null) return;
        Stack s1 = new Stack();
        Stack s2 = new Stack();
        s1.push(root);
        while(!s1.isEmpty()){
            root = s1.pop();
            s2.push(root); // 弹出的节点压入另一个栈
            if(root.left != null){
                s1.push(root.left);// 与前序遍历压栈顺序相反
            }
            if(root.right != null){
                s1.push(root.right);
            }
        }

        while(!s2.isEmpty()){
            list.add(s2.pop().val);
        }

    }
}

层序遍历

class Solution {
    public List> levelOrder(TreeNode root) {
        List> ans = new ArrayList<>();
        if(root == null) return ans;
        Deque deque = new LinkedList<>(); // 层序遍历用队列
        deque.add(root);
        while(!deque.isEmpty()){
            int n = deque.size(); // 分层
            List level = new ArrayList<>();
            for(int i=0;i
                TreeNode node = deque.poll();// 队列：poll，add或者offer
                level.add(node.val);
                if(node.left != null) deque.add(node.left);
                if(node.right != null) deque.add(node.right);
            }
            ans.add(level);
        }
        return ans;
    }
}

层序遍历Ⅱ

自底向上的层序遍历。

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

class Solution {
    public List> levelOrderBottom(TreeNode root) {
        List> ans = new ArrayList<>();
        if(root == null) return ans;

        Stack> stack = new Stack<>(); // 存
        Deque deque = new LinkedList<>();
        deque.add(root);
        while(!deque.isEmpty()){
            int n = deque.size();
            List level = new LinkedList<>();
            for(int i=0;i
                root = deque.pop();
                level.add(root.val);
                if(root.left != null) deque.add(root.left);
                if(root.right != null) deque.add(root.right);
            }
            stack.push(level);
        }
        while (!stack.isEmpty()) {// 用栈倒出来
            ans.add(stack.pop());
        }

        return ans;
    }
}

class Solution {
    public List> levelOrderBottom(TreeNode root) {
        List> ans = new ArrayList<>();
        if(root == null) return ans;
        Deque deque = new LinkedList<>(); // 层序遍历用队列
        deque.add(root);
        while(!deque.isEmpty()){
            int n = deque.size(); // 分层
            List level = new ArrayList<>();
            for(int i=0;i
                TreeNode node = deque.poll();// 队列：poll，add或者offer
                level.add(node.val);
                if(node.left != null) deque.add(node.left);
                if(node.right != null) deque.add(node.right);
            }
            ans.add(0, level);// 一直往最前面插入level
        }
        return ans;
    }
}

锯齿形层序遍历

先得到层序遍历，再手动调整

class Solution {
    public List> zigzagLevelOrder(TreeNode root) {
        List> ans = new ArrayList<>();
        if(root == null) return ans;
        Deque deque = new LinkedList<>(); // 层序遍历用队列
        deque.add(root);
        while(!deque.isEmpty()){
            int n = deque.size(); // 分层
            List level = new ArrayList<>();
            for(int i=0;i
                TreeNode node = deque.poll();// 队列：poll，add或者offer
                level.add(node.val);
                if(node.left != null) deque.add(node.left);
                if(node.right != null) deque.add(node.right);
            }
            ans.add(level);
        }
        /
// 序列化
public static Queue inSerial(Node head) {
    Queue ans = new LinkedList<>();
    ins(head, ans);
    return ans;
}

public static void ins(Node head, Queue ans) {
    if (head == null) {
        ans.add(null);
    } else {
        ins(head.left, ans);
        ans.add(String.valueOf(head.value));
        ins(head.right, ans);
    }
}

后序

// 序列化
public static Queue posSerial(Node head) {
    Queue ans = new LinkedList<>();
    poss(head, ans);
    return ans;
}

public static void poss(Node head, Queue ans) {
    if (head == null) {
        ans.add(null);
    } else {
        poss(head.left, ans);
        poss(head.right, ans);
        ans.add(String.valueOf(head.value));
    }
}
// 反序列化
public static Node buildByPosQueue(Queue poslist) {
        if (poslist == null || poslist.size() == 0) {
            return null;
        }
        // 左右中  ->  stack(中右左)
        Stack stack = new Stack<>();
        while (!poslist.isEmpty()) {
            stack.push(poslist.poll());
        }
        return posb(stack);
    }

    public static Node posb(Stack posstack) {
        String value = posstack.pop();
        if (value == null) {
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        head.right = posb(posstack);
        head.left = posb(posstack);
        return head;
    }

层序

// 序列化
public static Queue levelSerial(Node head) {
    Queue ans = new LinkedList<>();
    if (head == null) {
        ans.add(null);
    } else {
        ans.add(String.valueOf(head.value));
        Queue queue = new LinkedList();
        queue.add(head);
        while (!queue.isEmpty()) {
            head = queue.poll(); // head 父   子
            if (head.left != null) {
                ans.add(String.valueOf(head.left.value));
                queue.add(head.left);
            } else {
                ans.add(null);
            }
            if (head.right != null) {
                ans.add(String.valueOf(head.right.value));
                queue.add(head.right);
            } else {
                ans.add(null);
            }
        }
    }
    return ans;
}
// 反序列化
public static Node buildByLevelQueue(Queue levelList) {
    if (levelList == null || levelList.size() == 0) {
        return null;
    }
    Node head = generateNode(levelList.poll());
    Queue queue = new LinkedList();
    if (head != null) {
        queue.add(head);
    }
    Node node = null;
    while (!queue.isEmpty()) {
        node = queue.poll();
        node.left = generateNode(levelList.poll());
        node.right = generateNode(levelList.poll());
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    return head;
}

子树最大二叉搜索子树的大小，节点

// 返回节点
public static Node maxSubBSTHead1(Node head) {
    if (head == null) {
        return null;
    }
    if (getBSTSize(head) != 0) {
        return head;
    }
    Node leftAns = maxSubBSTHead1(head.left);
    Node rightAns = maxSubBSTHead1(head.right);
    return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
}

// 获取大小	
public static int getBSTSize(Node head) {
    if (head == null) {
        return 0;
    }
    ArrayList arr = new ArrayList<>();
    in(head, arr);// 先中序把节点都存入list中
    for (int i = 1; i < arr.size(); i++) {
        if (arr.get(i).value <= arr.get(i - 1).value) {// 不满足升序则返回
            return 0;
        }
    }
    return arr.size();
}

public static void in(Node head, ArrayList arr) {
    if (head == null) {
        return;
    }
    in(head.left, arr);
    arr.add(head);
    in(head.right, arr);
}

二叉树节点数

遍历，求集合的大小
递归

public int countNodes(TreeNode root) {
    if (root == null){
        return 0;
    }
    return countNodes(root.left) + countNodes(root.right) + 1;
}

二叉树层数

private int countLevel(TreeNode root){
        if(root == null){
            return 0;
        }
        return Math.max(countLevel(root.left),countLevel(root.right)) + 1;
}

递归套路

public static Node maxSubBSTHead2(Node head) {
    if (head == null) {
        return null;
    }
    return process(head).maxSubBSTHead;
    //  return process(head).maxSubBSTSize; // 这样返回大小
}

// 每一棵子树
public static class Info {
    public Node maxSubBSTHead;
    public int maxSubBSTSize;
    public int min;
    public int max;

    public Info(Node h, int size, int mi, int ma) {
        maxSubBSTHead = h;
        maxSubBSTSize = size;
        min = mi;
        max = ma;
    }
}

public static Info process(Node X) {
    if (X == null) {
        return null;
    }
    Info leftInfo = process(X.left);
    Info rightInfo = process(X.right);
    int min = X.value;
    int max = X.value;
    Node maxSubBSTHead = null;
    int maxSubBSTSize = 0;
    if (leftInfo != null) {
        min = Math.min(min, leftInfo.min);
        max = Math.max(max, leftInfo.max);
        maxSubBSTHead = leftInfo.maxSubBSTHead;
        maxSubBSTSize = leftInfo.maxSubBSTSize;
    }
    if (rightInfo != null) {
        min = Math.min(min, rightInfo.min);
        max = Math.max(max, rightInfo.max);
        if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
            maxSubBSTHead = rightInfo.maxSubBSTHead;
            maxSubBSTSize = rightInfo.maxSubBSTSize;
        }
    }
    if ((leftInfo == null ? true : (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.value))
        && (rightInfo == null ? true : (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.value))) {
        maxSubBSTHead = X;
        maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
            + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
    }
    return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
}

二叉树的堂兄弟节点

class Solution {
    // x 的信息
    int x;
    TreeNode xParent;
    int xDepth;
    boolean xFound = false;

    // y 的信息
    int y;
    TreeNode yParent;
    int yDepth;
    boolean yFound = false;

    public boolean isCousins(TreeNode root, int x, int y) {
        this.x = x;
        this.y = y;
        dfs(root, 0, null);
        return xDepth == yDepth && xParent != yParent;
    }

    public void dfs(TreeNode node, int depth, TreeNode parent) {
        if (node == null) {
            return;
        }

        if (node.val == x) {
            xParent = parent;
            xDepth = depth;
            xFound = true;
        } else if (node.val == y) {
            yParent = parent;
            yDepth = depth;
            yFound = true;
        }

        // 如果两个节点都找到了，就可以提前退出遍历
        // 即使不提前退出，对最坏情况下的时间复杂度也不会有影响
        if (xFound && yFound) {
            return;
        }

        dfs(node.left, depth + 1, node);

        if (xFound && yFound) {
            return;
        }

        dfs(node.right, depth + 1, node);
    }
}

二叉树算法

C/C++/C#相关栏目本月热门文章