目 录CONTENT

文章目录

Day14 | 树的遍历

RobKing
2023-09-19 / 0 评论 / 0 点赞 / 115 阅读 / 1,225 字

Day14 | 树的遍历

前序递归遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    res := make([]int, 0)
    dfs(root, &res)
    return res
}

func dfs(root *TreeNode, res *[]int) {
    if root == nil {
        return
    }
    *res = append(*res, root.Val)
    dfs(root.Left, res)
    dfs(root.Right, res)
}

C++实现

struct TreeNode {
	int val;
	TreeNode * left;
	TreeNode * right;
	TreeNode(): val(0), left(nullptr), right(nullptr);
	TreeNode(int val): val(val), left(NULL), right(NULL);
	TreeNode(int val, TreeNode * left, TreeNode * right): val(val), left(left), right(right);
};

class Solution {
public:
	vector<int> preorderTraversal(TreeNode* root) {
        if(root == nullptr) return {};
        vector<int> res;
        dfs(root, res);
        return res;
    }    
    void dfs(TreeNode * root, vector<int> &res) {
        if(root == nullptr) return;
        res.push_back(root->val);
        dfs(root->left, res);
        dfs(root->right, res);
        return;
    }
};

前序非递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    // 思路:使用一个栈保存所有的节点
    if root == nil {
        return nil
    }
    res := make([]int, 0)
    st := make([]*TreeNode, 0)
    st = append(st, root)
    for len(st) != 0 {
        // 出栈
        top := st[len(st)-1]
        res = append(res, top.Val)
        st = st[:len(st)-1]
        if top.Right != nil {
            st = append(st, top.Right)
        }
        if top.Left != nil {
            st = append(st, top.Left)
        }
    }
    return res
}

C++实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(root == nullptr) return {};
        vector<int> res;
        stack<TreeNode *> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode * top = st.top();
            res.push_back(top->val);
            st.pop();
            if(top->right) st.push(top->right); // 右边先入栈,这样就后出来
            if(top->left) st.push(top->left);
        }
        return res;
    }
};

后序非递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    // 思路:后序 左右中,和 中右左 刚好相反
    if root == nil {
        return nil
    }
    res := make([]int, 0)
    st := make([]*TreeNode, 0)
    st = append(st, root)
    for len(st) != 0 {
        top := st[len(st)-1]
        res = append(res, top.Val)
        st = st[:len(st)-1]
        if top.Left != nil {
            st = append(st, top.Left)
        }
        if top.Right != nil {
            st = append(st, top.Right)
        }
    }
    for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
        res[i], res[j] = res[j], res[i]
    }
    return res
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        // 后序顺序为 左右中  可以通过和前序一样的方法到达 中右左,然后翻转即可变成 左右中
        if(root == nullptr) return {};
        vector<int> res;
        stack<TreeNode *> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode * top = st.top();
            st.pop();
            res.push_back(top->val);
            if(top->left) st.push(top->left);
            if(top->right) st.push(top->right);
        }
        // 记得一定要翻转
        reverse(res.begin(), res.end());
        return res;
    }
};

中序非递归遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    // 思路:这一题的核心在于访问和处理的顺序不一样,所以需要借用指针来控制访问的顺序,栈用来处理元素
    if root == nil {
        return nil
    }
    st := make([]*TreeNode, 0)
    res := make([]int, 0)
    cur := root
    // 注意结束的条件: 栈中的元素全部处理完毕,指针也到达了根节点
    for len(st) != 0 || cur != nil {
        // 访问顺序是 左中右
        if cur != nil {
            st = append(st, cur)
            cur = cur.Left
        } else {
            // 达到根节点了,开始处理
            top := st[len(st)-1]
            res = append(res, top.Val)
            st = st[:len(st)-1]
            cur = top.Right
        }
    }
    return res

}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == nullptr) return {};
        stack<TreeNode *> st;
        vector<int> res;
        TreeNode * cur = root;
        // 循环条件是或的关系 一方面是到达了叶子结点,另一方面是左边处理完了,这个时候栈为空但是右边还没处理
        while(cur != nullptr || !st.empty()) {
            if(cur != nullptr) {
                // 没有到结尾
                st.push(cur);
                cur = cur->left;	// 一直往左走(左)
            }else {
                cur = st.top();	
                st.pop();
                res.push_back(cur->val);	// 中间的(中)
                cur = cur->right; 	// 右边走(右)
            }
        }
        return res;
    }
};

总结

递归三要素

  1. 确定递归函数的参数和返回值: 注意参数是否需要使用指针,一般来说全局变量需要用数组指针
  2. 确定终止条件
  3. 确定单层递归的逻辑
  • 今天的三种遍历方式都是非常简单的,特别是递归遍历
  • 对于非递归遍历来说,前序后后序使用的方法相同,使用栈来保存节点
  • 中序非递归遍历稍稍有点复杂,主要是因为遍历的顺序和处理的顺序不同,所以需要一个指针来作为访问的顺序,同样使用栈保存节点。指针一直往左,当处理的时候取出栈顶,这个时候将右指针加入到栈中,下次就会接着处理
0

评论区