二叉树遍历

前序遍历非递归

中->左->右

public List<Integer> preorder(TreeNode root){
    LinkedList<Integer> ret = new LinkedList<>();
    if(root == null)return ret;
    Deque<TreeNode> q = new LinkedList<>();
    q.offerLast(root);
    while(!q.isEmpty()){
        TreeNode node = q.pollLast();
        ret.add(node.val);
        if(node.right != null)q.offerLast(node.right);
        if(node.left != null)q.offerLast(node.left);
    }
    return ret;
}

中序遍历非递归

有左节点就一直压栈，压不动了就poll打印，之后转右节点

    public List<Integer> inorderTraversal(TreeNode root) {
        LinkedList<Integer> ret = new LinkedList<>();
        Deque<TreeNode> q = new LinkedList<>();
        while(root != null || !q.isEmpty()){
            while(root != null){
                q.offerLast(root);
                root = root.left;
            }
            root = q.pollLast();
            ret.add(root.val);
            root = root.right;
        }
        return ret;
    }

后序遍历非递归

几乎和前序一样，这样面试容易写出来

中->右->左，然后利用头插法

    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> ret = new LinkedList<>();
        Deque<TreeNode> q = new LinkedList<>();
        if(root == null)return ret;
        q.offerLast(root);
        while(!q.isEmpty()){
            TreeNode node = q.pollLast();
            ret.addFirst(node.val);
            if(node.left != null)q.offerLast(node.left);
            if(node.right != null)q.offerLast(node.right);
        }
        return ret;
    }

复杂的

这写法一写就废

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        Set<TreeNode> seen = new HashSet<>();
        while (root != null || !s.isEmpty()) {
            if (root == null && seen.contains(s.peek())) {
                ans.add(s.pop().val);
            } else if (root == null) {
                seen.add(s.peek());
                root = s.peek().right;
            } else {
                s.push(root);
                root = root.left;
            }
        }
        return ans;
    }
}

前序遍历

从前序与中序遍历序列构造二叉树

做选择题做过，其实是一个思路。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int length = preorder.size();
        TreeNode* root = preSort(preorder,0,length-1,inorder,0,length-1);
        return root;
    }
    TreeNode* preSort(vector<int>& preorder,int pl,int pr,vector<int>& inorder,int il,int ir){
        if(pl>pr)return nullptr;
        TreeNode* root = new TreeNode(preorder[pl]);
        int m = preorder[pl];
        int i;
        for(i = il; i <= ir; ++i){
            if(inorder[i] == m){
                break;
            }
        }
        int len = i-il+1;
        root->left=preSort(preorder,pl+1,pl+len-1,inorder,il,i-1);
        root->right=preSort(preorder,pl+len,pr,inorder,i+1,ir);
        return root;        
    }
};

这题就是参数多了点。

中序遍历

LeetCode 99. 恢复二叉搜索树

一开始我是这样写的：

class Solution {
public:
    TreeNode* pre = new TreeNode();
    void recoverTree(TreeNode* root) {
        midFunc(root);
        return;
    }
    void midFunc(TreeNode* root){
        if(root == nullptr){
            return;
        }
        midFunc(root->left);
        if(pre && root->val<pre->val){
            swap(root->val,pre->val);
        }
        pre = root;
        midFunc(root->right);
    }
};

考虑的还是太片面了，下面这种情况就没办法通过：

思考一下，第一步是比较3和2的大小，然后2和3交换，然后就是3和1的比较，发现1<3，又交换。问题就出现了，它不会比较根节点和跟节点的左节点！！！整个结果都是错的。

所以说不能只记录前一个节点，不能只考虑两个节点的关系，要考虑三个节点：前一个元素 < 当前元素 < 后一个元素

如下图所示，中序遍历顺序是 4,2,3,1，我们只要找到节点 4 和节点 1 交换顺序即可

这里我们有个规律发现这两个节点：

1. 第一个节点，是第一个按照中序遍历时候前一个节点大于后一个节点，我们选取前一个节点，这里指节点 4
2. 第二个节点，是在第一个节点找到之后，后面出现前一个节点大于后一个节点，我们选择后一个节点，这里指节点 1

注意审题：该树中的两个节点被错误地交换，只有两个节点错了！！！

class Solution {
    //记录那两个节点
    TreeNode firstNode = null;
    TreeNode secondNode = null;
    TreeNode preNode = new TreeNode(Integer.MIN_VALUE);

    public void recoverTree(TreeNode root) {

        in_order(root);
        int tmp = firstNode.val;
        firstNode.val = secondNode.val;
        secondNode.val = tmp;
    }

    private void in_order(TreeNode root) {
        if (root == null) return;
        in_order(root.left);
        //记录第一个错误节点
        if (firstNode == null && preNode.val > root.val) 
            firstNode = preNode;
        //记录第二个错误节点
        if (firstNode != null && preNode.val > root.val) 
            secondNode = root;
        preNode = root;
        in_order(root.right);
    }
}

以后换回Java写了。

后序遍历

124. 二叉树中的最大路径和

class Solution {
public:
    //最大路径和
    int result = INT_MIN;
    int maxPathSum(TreeNode* root) {
        fun(root);
        return result;
    }
    int fun(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        //比0小的话直接抛弃
        int left = max(0,fun(root->left));
        int right = max(0,fun(root->right));
        result = max(result,root->val+left+right);
        //路径只能左右中选其一
        return max(left,right)+root->val;
    }
};