遍历

代码形式采用leetcode Solution

中序

变形：第k小元素

class Solution {
    //递归
    private void inOrder(List<Integer> list, TreeNode root) {
        if(root == null)
            return;
        inOrder(list, root.left);
        list.add(root.val);
        inOrder(list, root.right);
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList();
        // inOrder(ret, root);
        //非递归
        Stack<TreeNode> stack = new Stack();
        TreeNode node = root;
        while(node != null || !stack.isEmpty()) {
            if(node == null) {
                node = stack.pop();
                ret.add(node.val);
                node = node.right;
                continue;
            }
            stack.push(node);
            node = node.left;
        }
        return ret;
    }
}

前序

class Solution {
    //递归
    public void preOrder(List<Integer> list, TreeNode root) {
        if(root==null)
            return;
        list.add(root.val);
        preOrder(list, root.left);
        preOrder(list, root.right);
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList();
        // preOrder(ret, root);
        //非递归
        Stack<TreeNode> s = new Stack();
        TreeNode node = root;
        while(node != null || !s.isEmpty()) {
            if(node == null) {
                node = s.pop();
                node = node.right;
                continue;
            }
            ret.add(node.val);
            s.push(node);
            node=node.left;
        }
        return ret;
    }
}

后序

class Solution {
    //递归
    public void postOrder(List<Integer> list, TreeNode root) {
        if(root == null)
            return;
        postOrder(list, root.left);
        postOrder(list, root.right);
        list.add(root.val); 
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList();
        // postOrder(ret, root);
        //非递归
        Stack<TreeNode> s = new Stack();
        TreeNode node = root;
        Map<TreeNode, Boolean> traversaled = new HashMap();
        while (node != null || !s.isEmpty()) {
            if(node == null) {
                node = s.pop();
                Boolean state = traversaled.get(node);
                if (state==null || state==false) {
                    s.push(node);
                    traversaled.put(node, true);
                    node = node.right;
                    continue;
                }
                ret.add(node.val);
                //这里比较骚，不能pop，否则死循环
                node = null;
                continue;
            }
            s.push(node);
            node = node.left;
        }
        return ret;
    }
}

高度

class Solution {
    //递归
    // public int maxDepth(TreeNode root) {
    //     if(root == null)
    //         return 0;
    //     return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    // }
    //非递归
    public int maxDepth(TreeNode root) {
        if(root == null)
            return 0;
        int depth = 0;
        TreeNode node = root;
        Queue<TreeNode> queue = new LinkedList();
        int cnt = 1;
        int next = 1;
        queue.offer(node);
        while(!queue.isEmpty()) {
            depth++;
            cnt = next;
            next = 0;
            while(cnt > 0) {
                node = queue.poll();
                cnt--;
                if (node.left != null){
                    queue.offer(node.left);
                    next++;
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    next++;
                }
            }
        }
        return depth;
    }
}

判断是否平衡

class Solution {
    //照搬c++思路，賊几把不优雅  
    private static class Depth {
        int val;
    }
    
    private boolean getDepth(TreeNode root, Depth depth) {
        if(root == null) {
            depth.val=0;
            return true;
        }
        Depth left = new Depth();
        Depth right = new Depth();
        boolean l = getDepth(root.left, left);
        boolean r = getDepth(root.right, right);
        depth.val = 1 + Math.max(left.val, right.val);
        if (l && r) {
            return Math.abs(left.val-right.val) <= 1;
        }
        return false;
    }
    public boolean isBalanced(TreeNode root) {
        Depth depth = new Depth();
        return getDepth(root, depth);
    }
}